Algorytmy i Struktury Danych - Punkty artykulacji w grafie

Naiwny sposób rozwiązania tego problemu jest następujący:

Obliczamy wstępnie liczbę spójnych składowych w grafie (możemy tutaj wykorzystać algorytm opisany w rozdziale o spójnych składowych) i zapamiętujemy ją. Następnie przechodzimy przez kolejne wierzchołki grafu. Każdy bieżący wierzchołek usuwamy wraz ze wszystkimi incydentnymi z nim krawędziami i ponownie obliczamy liczbę spójnych składowych. Jeśli jest ona większa od zapamiętanej, to usunięty wierzchołek jest punktem artykulacji i zapamiętujemy go na liście. Wierzchołek wstawiamy z powrotem wraz ze wszystkimi usuniętymi poprzednio krawędziami i przechodzimy do następnego wierzchołka. Gdy algorytm zakończy działanie, lista będzie zawierała wszystkie punkty artykulacji grafu

Algorytm naiwny wyszukiwania punktów artykulacji w grafie nieskierowanym

Wejście:

n	:	liczba wierzchołków w grafie, n ∈ C.
graf	:	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

lista par wierzchołków, które tworzą krawędzie-mosty.

Elementy pomocnicze:

ccn (n, graf)	:	funkcja zwracająca liczbę spójnych składowych w grafie.
nc	:	liczba spójnych składowych grafu, nc ∈ C.
v	:	numery wierzchołka grafu, v ∈ C.

Lista kroków:

K01:	Utwórz pustą listę L
K02:	nc ← ccn (n, graf)	zapamiętujemy liczbę spójnych składowych
K03:	Dla v = 0, 1, …, n-1, wykonuj kroki K04…K06	przechodzimy przez kolejne wierzchołki grafu
K04:	Usuń wierzchołek v z grafu wraz z jego krawędziami
K05:	Jeśli ccn (v, graf) > nc, to dodaj v do L	jeśli v jest punktem artykulacji, to zapamiętujemy go w L
K06:	Odtwórz wierzchołek v w grafie wraz z jego krawędziami
K07:	Zakończ	punkty artykulacji w L

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję grafu nieskierowanego, wyszukuje w nim wszystkie punkty artykulacji i wypisuje je w oknie konsoli. Ponieważ usuwanie i odtwarzanie wierzchołka grafu może być kłopotliwe, zastosowaliśmy dodatkową tablicę logiczną VU. Elementy tej tablicy odpowiadają wierzchołkom grafu. Wierzchołek obecny w grafie ma w tej tablicy wartość true. Wierzchołek usunięty ma wartość false.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

8 11
0 1 0 2 0 3 0 5
1 4 1 5
2 3
3 6 3 7
4 5
6 7

Pascal

// Wyszukiwanie punktów artykulacji w grafie nieskierowanym
// Data: 29.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------------------------------

program artpnts;

// Typy dla dynamicznej tablicy list sąsiedztwa, stosu i listy punktów artykulacji

type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------

Stack = object
  private
    S : PSLel;  // lista przechowująca stos

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push (v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor Stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------

destructor Stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function Stack.empty : boolean;
begin
  if S = nil then empty := true else empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function Stack.top : integer;
begin
  top := S^.v;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push (v : integer);
var
  e : PSLel;
begin
  new (e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e :PSLel;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.next;
    dispose (e);
  end;
end;

// Funkcja oblicza liczbę spójnych składowych w grafie
// n   -liczba wierzchołków w grafie
// graf-tablica list sąsiedztwa
// VU  -tablica dostępności krawędzi grafu
//----------------------------------------------------
function ccn (n : integer; var graf : TList; VU : array of boolean) : integer;
var
  C        : array of integer;
  S        : Stack;
  cc, i, v, u : integer;
  p        : PSLel;

begin
  S.init;                  // Tworzymy pusty stos
  SetLength (C, n);      // Tworzymy tablicę spójnych składowych
  for i := 0 to n-1 do
    C [i] := 0;          // Zerujemy tablicę spójnych składowych

  cc := 0;                 // Zerujemy licznik spójnych składowych

  for i := 0 to n-1 do
    if VU [i] and (C [i] = 0) then // Szukamy nieodwiedzonego jeszcze wierzchołka
    begin
      inc (cc);          // Zwiększamy licznik składowych
      S.push (i);        // Na stosie umieszczamy numer bieżącego węzła
      C [i] := cc;       // Wierzchołek numerujemy i oznaczamy jako odwiedzony
      while not S.empty do // Przechodzimy graf algorytmem DFS
      begin
        v := S.top();     // Pobieramy wierzchołek
        S.pop();          // Usuwamy go ze stosu
        p := graf [v];   // Przeglądamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          u := p^.v;
          if VU [u] and (C [u] = 0) then
          begin
            S.push (u);  // Na stos idą sąsiedzi nieodwiedzeni
            C [u] := cc  // i ponumerowani
          end;
          p := p^.next;
        end;
      end;
    end;

  SetLength (C, 0);      // Usuwamy tablicę C
  S.destroy;               // Usuwamy stos
  ccn := cc;               // Zwracamy wynik
end;

// **********************
// *** Program główny ***
// **********************

var
  n, m      : integer;     // Liczba wierzchołków i krawędzi
  A        : TList;        // Tablica list sąsiedztwa
  nc, i, v, u : integer;
  L, p, r    : PSLel;
  VU       : array of boolean;

begin
  read (n, m);           // Odczytujemy liczbę wierzchołków i krawędzi

  SetLength (A, n);      // Tworzymy tablice dynamiczne
  SetLength (VU, n);

  for i := 0 to n-1 do
  begin
    A [i]  := nil;
    VU [i] := true;
  end;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m-1 do
  begin
    read (v, u);         // Wierzchołki tworzące krawędź
    new (p);             // Tworzymy nowy element
    p^.v := u;             // Numerujemy go jako w
    p^.next := A [v];    // Dodajemy go na początek listy A [v]
    A [v] := p;
    new (p);             // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := A [u];
    A [u] := p;
  end;

  // Algorytm znajdowania punktów artykulacji

  L := nil;                // Pusta lista punktów artykulacji

  nc := ccn (n, A, VU);  // Zapamiętujemy liczbę spójnych składowych

  for v := 0 to n-1 do   // Przechodzimy przez kolejne wierzchołki grafu
  begin
    VU [v] := false;     // Zaznaczamy wierzchołek v jako usunięty
    if ccn (n, A, VU) > nc then // Sprawdzamy, czy v jest punktem artykulacji
    begin
      new (p);           // Jeśli tak, dołączamy go do listy
      p^.v := v;
      p^.next := L;
      L := p;
    end;
    VU [v] := true;      // Odtwarzamy wierzchołek
  end;

  writeln;

  // Wypisujemy znalezione punkty artykulacji, jednocześnie usuwając listę L

  while L <> nil do
  begin
    write (L^.v, ' ');
    p := L;
    L := L^.next;
    dispose (p);
  end;

  writeln;

  // Usuwamy pozostałe struktury dynamiczne

  for i := 0 to n-1 do
  begin
    p := A [i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
  end;

  SetLength (A, 0);
  SetLength (VU, 0);

end.

C++

// Wyszukiwanie punktów artykulacji w grafie nieskierowanym
// Data: 29.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa, stosu i listy punktów artykulacji

struct SLel
{
  SLel * next;
  int v;
};

class Stack
{
  private:
    SLel * S;   // lista przechowująca stos

  public:
    Stack();       // konstruktor
    ~Stack();      // destruktor
    bool empty (void);
    int  top (void);
    void push (int v);
    void pop (void);
};

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
Stack::Stack()
{
  S = NULL;
}

// Destruktor-zwalnia tablicę dynamiczną
//----------------------------------------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty (void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top (void)
{
  return S->v;
}

// Zapisuje na stos
//-----------------
void Stack::push (int v)
{
  SLel * e = new SLel;
  e->v    = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop (void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Funkcja oblicza liczbę spójnych składowych w grafie
// n   -liczba wierzchołków w grafie
// graf-tablica list sąsiedztwa
// VU  -tablica dostępności krawędzi grafu
//----------------------------------------------------
int ccn (int n, SLel ** graf, bool * VU)
{
  int * C, cc, i, v, u;
  Stack S;
  SLel * p;

  C = new int [n];         // Tworzymy tablicę spójnych składowych

  for(i = 0; i < n; i++) C [i] = 0; // Zerujemy tablicę spójnych składowych

  cc = 0;                    // Zerujemy licznik spójnych składowych

  for(i = 0; i < n; i++)
    if(VU [i] && !C [i]) // Szukamy nieodwiedzonego jeszcze wierzchołka
    {
      cC++;                  // Zwiększamy licznik składowych
      S.push (i);          // Na stosie umieszczamy numer bieżącego węzła
      C [i] = cc;          // Wierzchołek numerujemy i oznaczamy jako odwiedzony
      while(!S.empty())   // Przechodzimy graf algorytmem DFS
      {
        v = S.top();        // Pobieramy wierzchołek
        S.pop();            // Usuwamy go ze stosu
        for(p = graf [v]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka v
        {
          u = p->v;
          if(VU [u] && !C [u])
          {
            S.push (u);    // Na stos idą sąsiedzi nieodwiedzeni
            C [u] = cc;    // i ponumerowani
          }
        }
      }
    }

  delete [] C;              // Usuwamy tablicę C
  return cc;                 // Zwracamy wynik
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m;                  // Liczba wierzchołków i krawędzi
  SLel ** A;              // Tablica list sąsiedztwa
  int nc, i, v, u;
  SLel * L, * p, * r;
  bool * VU;

  cin >> n >> m;             // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy zmienne dynamiczne

  VU = new bool [n];       // Krawędzie aktywne
  A  = new SLel * [n];  // Tablica list sąsiedztwa

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++)
  {
    A [i] = NULL;
    VU [i] = true;
  }

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;
    p = new SLel;
    p->v = u;
    p->next = A [v];
    A [v] = p;
    p = new SLel;
    p->v = v;
    p->next = A [u];
    A [u] = p;
  }

  // Algorytm znajdowania punktów artykulacji

  L = NULL;                // Pusta lista punktów artykulacji

  nc = ccn (n, A, VU);   // Zapamiętujemy liczbę spójnych składowych

  for(v = 0; v < n; v++) // Przechodzimy przez kolejne wierzchołki grafu
  {
    VU [v] = false;      // Zaznaczamy wierzchołek v jako usunięty
    if(ccn (n, A, VU) > nc) // Sprawdzamy, czy v jest punktem artykulacji
    {
      p = new SLel;     // Jeśli tak, dołączamy go do listy
      p->v = v;
      p->next = L;
      L = p;
    }
    VU [v] = true;       // Odtwarzamy wierzchołek
  }

  cout << endl;

  // Wypisujemy znalezione punkty artykulacji, jednocześnie usuwając listę L

  while(L)
  {
    cout << L->v << " ";
    p = L;
    L = L->next;
    delete [] p;
  }

  cout << endl;

  // Usuwamy dynamiczne struktury danych

  for(i = 0; i < n; i++)
  {
    p = A [i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] A;
  delete [] VU;

  return 0;}

Basic

' Wyszukiwanie punktów artykulacji w grafie nieskierowanym
' Data: 29.12.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa, stosu i listy punktów artykulacji

Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    S As SLel Ptr  ' lista zawierająca stos
  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function top As Integer
    Declare Sub push (ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu Stack
'---------------------

' Konstruktor
'------------
Constructor Stack()
  S = 0
End Constructor

' Destruktor
'-----------
Destructor Stack()
  While S
  	 pop()
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function Stack.empty() As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function Stack.top() As Integer
  top = S->v
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push (ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop()
  Dim e As SLel Ptr
  If S Then
    e = S
    S = S->Next
    Delete e
  End If
End Sub

' Funkcja oblicza liczbę spójnych składowych w grafie
' n   -liczba wierzchołków w grafie
' graf-tablica list sąsiedztwa
' VU  -tablica dostępności krawędzi grafu
'----------------------------------------------------
Function ccn (ByVal n As Integer, ByVal graf As SLel Ptr ptr, ByVal VU As Byte Ptr) As Integer

  Dim As Integer Ptr C
  Dim As Integer cc, i, v, u
  Dim As Stack S
  Dim As SLel Ptr p

  C = New Integer [n]   ' Tworzymy tablicę spójnych składowych

  For i = 0 To n-1
    C [i] = 0           ' Zerujemy tablicę spójnych składowych
  Next

  cc = 0                  ' Zerujemy licznik spójnych składowych

  For i = 0 To n-1
    if(VU [i] = 1) AndAlso (C [i] = 0) Then ' Szukamy nieodwiedzonego jeszcze wierzchołka
      cc += 1             ' Zwiększamy licznik składowych
      S.push (i)        ' Na stosie umieszczamy numer bieżącego węzła
      C [i] = cc        ' Wierzchołek numerujemy i oznaczamy jako odwiedzony     
      While S.empty() = 0 ' Przechodzimy graf algorytmem DFS
        v = S.top()      ' Pobieramy wierzchołek
        S.pop()          ' Usuwamy go ze stosu
        p = graf [v]    ' Przeglądamy sąsiadów wierzchołka v
        While p
          u = p->v
          if(VU [u] = 1) Andalso (C [u] = 0) Then
            S.push (u)  ' Na stos idą sąsiedzi nieodwiedzeni
            C [u] = cc  ' i ponumerowani
          End If
          p = p->Next
        Wend
      Wend
    End If
  Next
 
  Delete [] C            ' Usuwamy tablicę C

  Return cc               ' Zwracamy wynik

End Function

' **********************
' *** Program główny ***
' **********************

Dim As Integer n, m, nc, i, v, u
Dim As SLel Ptr Ptr A
Dim As SLel Ptr L, p, r
Dim As Byte Ptr VU

Open Cons For Input As #1

Input #1, n, m            ' Odczytujemy liczbę wierzchołków i krawędzi

A = New SLel Ptr [n] ' Tworzymy tablice dynamiczne
VU = New Byte [n]       ' Krawędzie aktywne

' Tablicę A wypełniamy pustymi listami, a tablicę C wypełniamy zerami

For i = 0 To n-1
  A [i] = 0
  VU [i] = 1
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 0 To m-1
  Input #1, v, u        ' Wierzchołki tworzące krawędź
  p = new SLel       ' Tworzymy nowy element
  p->v = u              ' Numerujemy go jako u
  p->next = A [v]     ' Dodajemy go na początek listy A [v]
  A [v] = p
  p = new SLel       ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = A [u]
  A [u] = p
Next

' Algorytm znajdowania punktów artykulacji

L = 0                   ' Pusta lista punktów artykulacji

nc = ccn (n, A, VU)   ' Zapamiętujemy liczbę spójnych składowych

For v = 0 To n-1      ' Przechodzimy przez kolejne wierzchołki grafu
  VU [v] = 0          ' Zaznaczamy wierzchołek v jako usunięty
  If ccn (n, A, VU) > nc Then   ' Sprawdzamy, czy v jest punktem artykulacji
    p = New SLel     ' Jeśli tak, dołączamy go do listy
    p->v = v
    p->next = L
    L = p
  End If
  VU [v] = 1          ' Odtwarzamy wierzchołek
Next

Print

' Wypisujemy znalezione punkty artykulacji, jednocześnie usuwając listę L

While L
  print L->v;
  p = L
  L = L->Next
  Delete [] p
Wend

Print

' Usuwamy dynamiczne struktury danych

For i = 0 To n-1
  p = A [i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] A
Delete [] VU

End

Wynik:
8 11 0 1 0 2 0 3 0 5 1 4 1 5 2 3 3 6 3 7 4 5 6 7 3 0

Na początek: podrozdziału strony

Do szybkiego wyszukiwania punktów artykulacji wykorzystujemy podobny algorytm jak do wyszukiwania mostów. Idea tego algorytmu również opiera się na drzewie rozpinającym grafu oraz na przejściu wstecznym za pomocą DFS. W algorytmie wykorzystuje się dwie własności punktów artykulacji:

obrazek

Korzeń drzewa rozpinającego w głąb grafu jest punktem artykulacji tylko wtedy, jeśli posiada co najmniej dwóch synów. Uzasadnienie tego faktu jest bardzo proste. Gdy uruchomimy przejście DFS przy tworzeniu drzewa rozpinającego, to dojdzie ono do każdego wierzchołka, do którego istnieje w grafie ścieżka od wierzchołka startowego. Zatem po uruchomieniu w korzeniu drzewa DFS odwiedzi wszystkich sąsiadów korzenia, do których w grafie istnieje ścieżka. Jeśli jakiś sąsiad zostanie nieodwiedzony przy powrocie z DFS uruchomionego dla pierwszego z synów, to znaczy, że w grafie nie było do niego innej ścieżki oprócz krawędzi bezpośrednio od korzenia do tego sąsiada. W takim przypadku powstaje kolejny syn korzenia ( gdyż DFS musimy ponownie uruchomić dla każdego nieodwiedzonego sąsiada). Pomiędzy poprzednim synem istnieje droga tylko poprzez korzeń drzewa ( gdyby istniała inna, to DFS by ją znalazło i dany wierzchołek nie zostałby synem korzenia, lecz jego dalszym potomkiem). Jeśli korzeń zostanie teraz usunięty z grafu, to wszyscy jego synowie na drzewie rozpinającym znajdą się w oddzielnych spójnych składowych grafu. Liczba tych składowych wzrośnie, zatem korzeń będzie punktem artykulacji.

obrazek

Wierzchołek nie będący korzeniem drzewa rozpinającego w głąb jest punktem artykulacji, jeśli przynajmniej dla jednego z jego synów nie istnieje krawędź wtórna, która łączy potomka tego wierzchołka z jego przodkiem. Wyjaśnienie jest również proste. Istnienie krawędzi wtórnej oznacza, że do syna można dojść również inną drogą, która nie wiedzie poprzez dany wierzchołek. Skoro tak, to jego usunięcie nie odłączy syna od reszty grafu, gdyż wciąż będzie się znajdował w tej samej spójnej składowej z uwagi na krawędź łączącą jego potomków z innym przodkiem. Zatem liczba składowych nie wzrośnie. Jeśli natomiast taka krawędź wtórna nie istnieje, to do tego syna można przejść w grafie tylko krawędzią, która łączy go z jego ojcem. Jeśli usuniemy ojca, krawędź zniknie i syn znajdzie się w oddzielnej spójnej składowej. Liczba składowych grafu wzrośnie, zatem ojciec musi być punktem artykulacji.

Sprawdzenie pierwszej własności jest proste. Drugą własność sprawdzamy następująco:

Przechodzimy przez graf algorytmem DFS, numerując po drodze wszystkie odwiedzone wierzchołki oraz obliczając dla nich parametr Low po odwiedzeniu wszystkich sąsiadów. Przypomnijmy, parametr Low jest najmniejszą wartością z numerów nadanych przez DFS bieżącemu wierzchołkowi, wierzchołkowi połączonemu z bieżącym krawędzią wtórną oraz parametrom Low wszystkich synów na drzewie rozpinającym. Czym dokładnie jest ten parametr dla danego wierzchołka? Otóż jest to najmniejszy numer nadany przez DFS wierzchołkowi, do którego istnieje ścieżka w dół drzewa (później ścieżka ta może zawracać i tworzyć cykl). Jeśli parametr Low dla jednego z synów będzie większy lub równy numerowi DFS bieżącego wierzchołka, to będzie to oznaczało, że ścieżka zawierająca wierzchołek bieżący i tego syna nie posiada krawędzi wtórnej do przodka wierzchołka bieżącego (w takim przypadku parametr Low syna byłby mniejszy od numeru DFS jego ojca). Skoro tak, to wierzchołek bieżący jest punktem artykulacji.

Zobaczmy na prostym przykładzie, jak działa algorytm Tarjana:

	Oto nasz przykładowy graf, w którym mamy znaleźć wszystkie punkty artykulacji. Graf przejdziemy algorytmem DFS, tworząc po drodze drzewo rozpinające w głąb oraz numerując wierzchołki grafu (numeracja DFS nie ma nic wspólnego z numerami wierzchołków w definicji grafu – określa ona kolejność odwiedzin poszczególnych wierzchołków). Numery te posłużą później do wyznaczenia dla każdego wierzchołka parametru Low, gdy zostaną już przetworzeni wszyscy sąsiedzi.
	Rozpoczynamy od wierzchołka 0 (punkt startowy nie ma wpływu na wynik pracy algorytmu). Wierzchołek zaznaczamy jako odwiedzony i nadajemy mu numer DFS 1. Wierzchołek posiada trzech nieodwiedzonych jeszcze sąsiadów: 1, 2 i 3.
	Odwiedzamy wierzchołek nr 1. Oznaczamy go jako odwiedzony i nadajemy mu numer DFS 2. Krawędź 0 – 1 staje się krawędzią drzewa rozpinającego w głąb. Wierzchołek 0 jest korzeniem drzewa, wierzchołek 1 jest jego synem. Wierzchołek posiada jednego nieodwiedzonego sąsiada: 2.
	Odwiedzamy wierzchołek 2. Oznaczamy go jako odwiedzony i nadajemy mu numer DFS 3. Krawędź 1 – 2 zostaje dopisana do drzewa rozpinającego (1 jest ojcem, 2 jest synem). Wierzchołek 2 nie posiada już nieodwiedzonych sąsiadów. Wierzchołek nie ma synów, nie może być zatem punktem artykulacji. Przetwarzamy go, obliczając parametr Low jako najmniejszą liczbę z 3 (numer DFS wierzchołka) i 1 (numer DFS wierzchołka 0, który łączy się krawędzią wtórną). Wierzchołek 2 nie posiada synów na drzewie rozpinającym. Low (2) = min (3, 1) = 1 Wracamy do wierzchołka nr 1.
	Jesteśmy z powrotem w wierzchołku nr 1. Wierzchołek posiada syna nr 2, lecz parametr Low (2) = 1 jest mniejszy od numeru DSF wierzchołka nr 1 równego 2 (a oznacza to, że istnieje krawędź wtórna łącząca potomka (2) z przodkiem (0): tutaj jest to krawędź 2 – 0). Zatem wierzchołek ten nie może być punktem artykulacji. Ponieważ wszyscy sąsiedzi zostali już odwiedzeni, przetwarzamy wierzchołek, obliczając dla niego parametr Low. Będzie to najmniejsza wartość z 2 (numer DFS wierzchołka) i 1 (parametr Low dla jego syna 2). Low (1) = min (2, 1) = 1. Wracamy do wierzchołka 0.
	Odwiedzamy ostatniego sąsiada wierzchołka 0, czyli wierzchołek nr 3. Oznaczamy go jako odwiedzony i nadajemy mu numer DFS 4. Krawędź 0 – 3 zostaje dopisana do drzewa rozpinającego. Wierzchołek nr 3 ma dwóch nieodwiedzonych sąsiadów: 4 i 5.
	Odwiedzamy wierzchołek nr 4. Oznaczamy go jako odwiedzonego i nadajemy mu numer DFS 5. Krawędź 3 – 4 zostaje dopisana do drzewa rozpinającego. Wierzchołek posiada jednego nieodwiedzonego sąsiada: 5.
	Odwiedzamy wierzchołek 5. Oznaczamy go jako odwiedzonego i nadajemy mu numer DFS 6. Krawędź 4 – 5 zostaje dopisana do drzewa rozpinającego. Wierzchołek nr 5 nie posiada nieodwiedzonych sąsiadów. Wierzchołek nr 5 nie posiada synów, nie może być punktem artykulacji. Wyliczamy parametr Low jako najmniejszą wartość z 6 (numer DFS wierzchołka) i 4 (numer DFS wierzchołka 3, który łączy się krawędzią wtórną). Low (5) = min (6, 4) = 4.
	Wracamy do wierzchołka nr 4. Wszyscy sąsiedzi są odwiedzeni. Wierzchołek nr 4 posiada syna 5, lecz parametr Low (5) jest mniejszy od numeru DFS wierzchołka. Zatem wierzchołek nr 4 nie jest punktem artykulacji. Obliczamy parametr Low jako najmniejszą wartość z 5 (numer DFS wierzchołka) i 4 (parametr Low jego syna 5). Low (4) = min (5, 4) = 4.
	Wracamy do wierzchołka nr 3. Zauważamy, iż parametr syna Low ( 4) = 4 spełnia kryterium punktu artykulacji ( jest większy lub równy numerowi DFS wierzchołka). Zatem wierzchołek nr 3 jest punktem artykulacji. Wyznaczamy parametr Low (3) jako najmniejszą wartość z 4 (numer DFS wierzchołka), 4 (parametr Low ( 4) syna na drzewie rozpinającym) i 6 (numer DFS wierzchołka 5 połączonego krawędzią wtórną). Low (3) = min (4, 4, 6) = 4.
	Wracamy do wierzchołka 0. Wszyscy sąsiedzi są odwiedzeni. Ponieważ wierzchołek 0 jest korzeniem drzewa rozpinającego, to sprawdzamy dla niego pierwsze kryterium. Posiada dwóch synów na drzewie rozpinającym, zatem jest punktem artykulacji (parametru Low nawet nie musimy dla niego obliczać, gdyż nie będzie on już dalej potrzebny).

Algorytm Tarjana wyszukiwania punktów artykulacji w grafie nieskierowanym

Funkcja rekurencyjna DFSap (v, vf, graf, D, dv, L)

Wejście:

v	:	wierzchołek startowy, v ∈ C.
vf	:	ojciec wierzchołka v na drzewie rozpinającym w głąb, vf ∈ C.
graf	:	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
D	:	tablica numerów DFS dla poszczególnych wierzchołków.
dv	:	referencja do zmiennej zewnętrznej przechowującej numery wierzchołków. Przy pierwszym wywołaniu zmienna powinna zawierać 2. dv ∈ C.
L	:	lista punktów artykulacji.

Wyjście:

Wartość parametru Low dla wierzchołka v. Jeśli zostanie znaleziony punkt artykulacji, to będzie on dopisany do listy L.

Elementy pomocnicze:

Low	:	wartość parametru Low dla bieżącego wierzchołka, Low ∈ C.
temp	:	chwilowo przechowuje wynik wywołania rekurencyjnego, t ∈ C.
test	:	zawiera wynik testu na punkt artykulacji.

Lista kroków:

K01:	D [v] ← dv	numerujemy wierzchołek
K02	Low ← dv	wstępna wartość parametru
K03:	dv ← dv+1	kolejny wierzchołek będzie miał numer o 1 większy
K04:	test ← false
K05:	Dla każdego sąsiada u wierzchołka v : wykonuj kroki K06…K12	przeglądamy wszystkich sąsiadów wierzchołka bieżącego
K06:	Jeśli u = vf, to następny obieg pętli K05	pomijamy ojca
K07:	Jeśli D [u] = 0, to idź do kroku K10	sąsiad nieodwiedzony?
K08:	Jeśli D [u] < Low, to Low ← D [u]	odwiedzony, krawędź wtórna. Modyfikujemy parametr Low
K09:	Następny obieg pętli K04
K10:	temp ← DFSb (u, v, graf, T, D, dv, L)	rekurencyjne wywołanie funkcji
K11:	Jeśli temp < Low, to Low ← temp	modyfikujemy parametr Low
K12:	Jeśli temp ≥ D [v], to test ← true	robimy test na punkt artykulacji
K13:	Jeśli test = true, to dodaj v do L	jeśli va jest punktem artykulacji, to dodajemy go do listy L
K14:	Zakończ z wynikiem Low

Algorytm główny

Wejście:

n	:	liczba wierzchołków w grafie, n ∈ C.
graf	:	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

lista numerów wierzchołków, które są punktami artykulacji.

Elementy pomocnicze:

dv	:	przechowuje numery wierzchołków dla DFS, dv ∈ C.
D	:	dynamiczna tablica dla numerów wierzchołków nadawanych przez DFS. Elementy są liczbami całkowitymi.
v, u	:	numery wierzchołków w grafie, v, u ∈ C.
nc	:	liczba synów na drzewie rozpinającym dla korzenia, nc ∈ C.

Lista kroków:

K01:	Twórz n elementową tablicę D
K02:	Zeruj tablicę D
K03:	Twórz pustą listę L
K04:	Dla v = 0, 1, …, n-1: wykonuj kroki K05…K13	przechodzimy przez kolejne wierzchołki grafu
K05:	Jeśli D [v] > 0, to następny obieg pętli K04	szukamy nieodwiedzonego wierzchołka
K06:	dv ← 2	początek numeracji DFS dla synów
K07:	nc ← 0	liczba synów na drzewie rozpinającym w głąb
K08:	D [v ] ← 1	korzeń ma zawsze numer DFS równy 1
K09:	Dla każdego sąsiada u wierzchołka v : wykonuj kroki K10…K12	przeglądamy sąsiadów
K10	Jeśli D [u] > 0, to następny obieg pętli K09	szukamy nieodwiedzonego sąsiada
K11:	nc ← nc+1	znaleźliśmy syna, zwiększamy licznik synów
K12:	DFSap (u, v, graf, D, dv, L)	wywołujemy przejście DFS
K13:	Jeśli nc > 1, to dodaj v do L	korzeń ma co najmniej dwóch synów - jest punktem artykulacji
K14:	Zakończ z wynikiem L

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję grafu nieskierowanego, wyszukuje w nim wszystkie punkty artykulacji i wyświetla je w oknie konsoli. Aby uprościć funkcję rekurencyjną DFSap(), większość jej parametrów została zrealizowana jako zmienne globalne.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

8 11
0 1 0 2 0 3 0 5
1 4 1 5
2 3
3 6 3 7
4 5
6 7

Pascal

// Wyszukiwanie punktów artykulacji w grafie nieskierowanym
// Data: 30.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------------------------------

program bridges;

// Typy dla dynamicznej tablicy list sąsiedztwa i listy punktów artykulacji
type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Zmienne globalne

var
  n, m, dv : integer;        // Liczba wierzchołków, krawędzi, numeracja
  graf   : TList;            // Tablica list sąsiedztwa
  D      : array of integer; // Numery DFS
  L      : PSLel;         // Lista mostów

// Funkcja rekurencyjna wyszukująca punkty artykulacji
// v -numer bieżącego wierzchołka
// vf-ojciec bieżącego wierzchołka na drzewie rozpinającym
// Reszta parametrów to zmienne globalne
//----------------------------------------------------------
function DFSap (v, vf : integer) : integer;
var
  Low, temp, u : integer;
  test       : boolean;
  p          : PSLel;
begin
  D [v] := dv;            // Numerujemy wierzchołek
  Low  := dv;               // Wstępna wartość parametru Low
  inc (dv);               // Następny numer wierzchołka
  test := false;
  p := graf [v];          // Przeglądamy listę sąsiadów
  while p <> nil do
  begin
    u := p^.v;              // u-numer wierzchołka sąsiada
    if u <> vf then         // u nie może być ojcem v
    begin
      if D [u] = 0 then   // Jeśli sąsiad u nie był odwiedzany, to
      begin
        temp := DFSap (u, v);   // rekurencyjnie odwiedzamy go
        if temp < Low then Low := temp;
        if temp >= D [v] then test := true; // Test na punkt artykulacji
      end
      else if D [u] < Low then Low := D [u];
    end;
    p := p^.next;           // Następny wierzchołek na liście
  end;

  // Wszyscy sąsiedzi zostali odwiedzeni, sprawdzamy wynik testu

  if test then
  begin
    new (p);              // Mamy nowy punkt artykulacji
    p^.v := v;
    p^.next := L;
    L := p;
  end;

  DFSap := Low;             // Wynik
end;

// **********************
// *** Program główny ***
// **********************

var
  i, u, v, nc : integer;    // Numery wierzchołków, licznik synów korzenia
  p, r      : PSLel;
begin
  read (n, m);            // Odczytujemy liczbę wierzchołków i krawędzi

  SetLength (graf, n);    // Tworzymy zmienne dynamiczne
  SetLength (D, n);
  L := nil;

  for i := 0 to n-1 do
  begin
    graf [i] := nil;
    D [i]    := 0;
  end;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m-1 do
  begin
    read (v, u);          // Wierzchołki tworzące krawędź
    new (p);              // Tworzymy nowy element
    p^.v := u;              // Numerujemy go jako w
    p^.next := graf [v];  // Dodajemy go na początek listy graf [v]
    graf [v] := p;
    new (p);              // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := graf [u];
    graf [u] := p;
  end;

  // Szukamy punktów artykulacji

  for v := 0 to n-1 do
    if D [v] = 0 then     // Szukamy nieodwiedzonego wierzchołka
    begin
      dv   := 2;            // Numer DFS dla pierwszego syna
      nc   := 0;            // Zerujemy licznik synów
      D [v] := 1;         // Korzeń zawsze ma numer DFS 1
      p := graf [v];      // Przeglądamy sąsiadów v
      while p <> nil do
      begin
        u := p^.v;          // Numer wierzchołka sąsiedniego
        if D [u] = 0 then // Szukamy nieodwiedzonego sąsiada
        begin
          inc (nc);       // Zwiększamy licznik synów
          DFSap (u, v);   // Szukamy punktów artykulacji w grafie
        end;
        p := p^.next;
      end;
      if nc > 1 then        // Czy korzeń jest punktem artykulacji?
      begin
        new (p);          // Tak, dodajemy go do listy
        p^.v := v;
        p^.next := L;
        L := p;
      end;
    end;

  writeln;

  // Wypisujemy znalezione punkty artykulacji

  while L <> nil do
  begin
    write (L^.v, ' ');
    p := L;
    L := L^.next;
    dispose (p);
  end;

  writeln;

  // Usuwamy struktury dynamiczne

  SetLength (D, 0);

  for i := 0 to n-1 do
  begin
    p := graf [i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
  end;

  SetLength (graf, 0);
end.

C++

// Wyszukiwanie punktów artykulacji w grafie nieskierowanym
// Data: 30.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i listy punktów artykulacji

struct SLel
{
  SLel * next;
  int v;
};

// Zmienne globalne

int n, m, dv;              // Liczba wierzchołków, krawędzi, numeracja
SLel ** graf;           // Tablica list sąsiedztwa
int *D;                    // Numery DFS
SLel * L;               // Lista mostów

// Funkcja rekurencyjna wyszukująca punkty artykulacji
// v -numer bieżącego wierzchołka
// vf-ojciec bieżącego wierzchołka na drzewie rozpinającym
// Reszta parametrów to zmienne globalne
//----------------------------------------------------------
int DFSap (int v, int vf)
{
  int Low, temp, u;
  bool test;
  SLel * p;

  D [v] = Low = dv++;

  test = false;

  for(p = graf [v]; p; p = p->next) // Przeglądamy listę sąsiadów
  {
    u = p->v;              // u-numer wierzchołka sąsiada
    if(u != vf)          // u nie może być ojcem v
    {
      if(!D [u])       // Jeśli sąsiad u nie był odwiedzany, to
      {
        temp = DFSap (u, v); // rekurencyjnie odwiedzamy go
        if(temp < Low) Low = temp;
        if(temp >= D [v]) test = true; // Test na punkt artykulacji
      }
      else if(D [u] < Low) Low = D [u];
    }
  }

  // Wszyscy sąsiedzi zostali odwiedzeni, sprawdzamy wynik testu

  if(test)
  {
    p = new SLel;       // Mamy nowy punkt artykulacji
    p->v = v;
    p->next = L;
    L = p;
  }

  return Low;              // Wynik
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int i, u, v, nc;         // Numery wierzchołków, licznik synów korzenia
  SLel *p, *r;

  cin >> n >> m;           // Odczytujemy liczbę wierzchołków i krawędzi

  graf = new SLel * [n]; // Tworzymy zmienne dynamiczne
  D = new int [n];
  L = NULL;

  for(i = 0; i < n; i++)
  {
    graf [i] = NULL;
    D [i]    = 0;
  }

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;         // Wierzchołki tworzące krawędź
    p = new SLel;       // Tworzymy nowy element
    p->v = u;              // Numerujemy go jako w
    p->next = graf [v];  // Dodajemy go na początek listy graf [v]
    graf [v] = p;
    p = new SLel;       // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf [u];
    graf [u] = p;
  }

  // Szukamy punktów artykulacji

  for(v = 0; v < n; v++)
    if(!D [v])         // Szukamy nieodwiedzonego wierzchołka
    {
      dv   = 2;            // Numer DFS dla pierwszego syna
      nc   = 0;            // Zerujemy licznik synów
      D [v] = 1;         // Korzeń zawsze ma numer DFS 1
      for(p = graf [v]; p; p = p->next) // Przeglądamy sąsiadów v
      {
        u = p->v;          // Numer wierzchołka sąsiedniego
        if(!D [u])     // Szukamy nieodwiedzonego sąsiada
        {
          nC++;            // Zwiększamy licznik synów
          DFSap (u, v);  // Szukamy punktów artykulacji w grafie
        }
      }

      if(nc > 1)         // Czy korzeń jest punktem artykulacji?
      {
        p = new SLel;   // Tak, dodajemy go do listy
        p->v = v;
        p->next = L;
        L = p;
      }
    }

  cout << endl;

  // Wypisujemy znalezione punkty artykulacji

  while(L)
  {
    cout << L->v << " ";
    p = L;
    L = L->next;
    delete p;
  }

  cout << endl;

  // Usuwamy struktury dynamiczne

  delete [] D;

  for(i = 0; i < n; i++)
  {
    p = graf [i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete graf;

  return 0;}

Basic

' Wyszukiwanie punktów artykulacji w grafie nieskierowanym
' Data: 30.12.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i listy punktów artykulacji

Type SLel
  next As SLel Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer n, m, dv      ' Liczba wierzchołków, krawędzi, numeracja
Dim Shared As SLel Ptr Ptr graf  ' Tablica list sąsiedztwa
Dim Shared As Integer Ptr D         ' Numery DFS
Dim Shared As SLel Ptr L         ' Lista mostów

' Funkcja rekurencyjna wyszukująca punkty artykulacji
' v -numer bieżącego wierzchołka
' vf-ojciec bieżącego wierzchołka na drzewie rozpinającym
' Reszta parametrów to zmienne globalne
'----------------------------------------------------------
Function DFSap (ByVal v As integer, byval vf As Integer) As Integer

  Dim As Integer Low, temp, u, test
  Dim As SLel Ptr p

  D [v] = dv: Low = dv: dv += 1

  test = 0

  p = graf [v]             ' Przeglądamy listę sąsiadów
  While p
    u = p->v                 ' u-numer wierzchołka sąsiada
    If u <> vf Then          ' u nie może być ojcem v
      If D [u] = 0 Then    ' Jeśli sąsiad u nie był odwiedzany, to
        temp = DFSap (u, v) ' rekurencyjnie odwiedzamy go
        If temp < Low Then Low = temp
        If temp >= D [v] Then test = 1 ' Test na punkt artykulacji
      Else
        if(D [u] < Low) Then Low = D [u]
      End If
    End If
    p = p->Next
  Wend

  ' Wszyscy sąsiedzi zostali odwiedzeni, sprawdzamy wynik testu

  If test = 1 Then
    p = New SLel          ' Mamy nowy punkt artykulacji
    p->v = v
    p->next = L
    L = p
  End If

  Return Low                 ' Wynik
End Function

' **********************
' *** Program główny ***
' **********************

Dim As Integer i, u, v, nc   ' Numery wierzchołków, licznik synów korzenia
Dim As SLel Ptr p, r

Open Cons For Input As #1

Input #1, n, m               ' Odczytujemy liczbę wierzchołków i krawędzi

graf = New SLel Ptr [n] ' Tworzymy zmienne dynamiczne
D    = New Integer [n]
L    = 0

For i = 0 To n-1
  graf [i] = 0
  D [i]    = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m-1
  Input #1, v, u          ' Wierzchołki tworzące krawędź
  p = new SLel         ' Tworzymy nowy element
  p->v = u                ' Numerujemy go jako u
  p->next = graf [v]    ' Dodajemy go na początek listy graf [v]
  graf [v] = p
  p = new SLel         ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = graf [u]
  graf [u] = p
Next

Close #1

' Szukamy punktów artykulacji

For v = 0 To n-1
  If D [v] = 0 Then     ' Szukamy nieodwiedzonego wierzchołka
    dv   = 2              ' Numer DFS dla pierwszego syna
    nc   = 0              ' Zerujemy licznik synów
    D [v] = 1           ' Korzeń zawsze ma numer DFS 1

    p = graf [v]        ' Przeglądamy sąsiadów v
    While p
      u = p->v            ' Numer wierzchołka sąsiedniego
      If D [u] = 0 Then ' Szukamy nieodwiedzonego sąsiada
        nc += 1           ' Zwiększamy licznik synów
        DFSap (u, v)    ' Szukamy punktów artykulacji w grafie
      End If
      p = p->Next
    Wend
   
    If nc > 1 Then        ' Czy korzeń jest punktem artykulacji?
      p = New SLel     ' Tak, dodajemy go do listy
      p->v = v
      p->next = L
      L = p
    End If
  End if
Next

Print

' Wypisujemy znalezione punkty artykulacji

While L
  print L->v;
  p = L
  L = L->Next
  Delete p
Wend

Print

' Usuwamy dynamiczne struktury danych

For i = 0 To n-1
  p = graf [i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] D
Delete [] graf

End

Wynik:
8 11 0 1 0 2 0 3 0 5 1 4 1 5 2 3 3 6 3 7 4 5 6 7 0 3

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Znajdowanie punktów artykulacji w grafie

Problem

Rozwiązanie nr 1

Algorytm naiwny wyszukiwania punktów artykulacji w grafie nieskierowanym

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm Tarjana wyszukiwania punktów artykulacji w grafie nieskierowanym

Funkcja rekurencyjna DFSap (v, vf, graf, D, dv, L)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm główny

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy