Znajdowanie punktów artykulacji w grafie


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
  Rozwiązanie nr 1
Rozwiązanie nr 2

Problem

Dla danego grafu nieskierowanego wyznaczyć wszystkie punkty artykulacji.



 

Punktem artykulacji (ang. articulation point lub cut vertex) jest wierzchołek, którego usunięcie z grafu spowoduje zwiększenie liczby spójnych składowych. Na powyższym rysunku punktem artykulacji jest wierzchołek nr 0.

 

Rozwiązanie nr 1

 

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:
L  –  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 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

 

Program

Ważne:

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.

 

Przykładowe dane:

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

 

Lazarus
// 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
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// Definicja typu obiektowego stack
//---------------------------------

stack = object
  private
    S : PslistEl;  // 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 : PslistEl;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure stack.pop;
var
  e :PslistEl;
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        : PslistEl;

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    : PslistEl;
  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.
Code::Blocks
// 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 slistEl
{
  slistEl * next;
  int v;
};

class stack
{
  private:
    slistEl * 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)
{
  slistEl * e = new slistEl;
  e->v    = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void stack::pop(void)
{
  if(S)
  {
    slistEl * 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, slistEl ** graf, bool * VU)
{
  int * C,cc,i,v,u;
  stack S;
  slistEl * 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
  slistEl ** A;              // Tablica list sąsiedztwa
  int nc,i,v,u;
  slistEl * 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 slistEl * [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 slistEl;
    p->v = u;
    p->next = A[v];
    A[v] = p;
    p = new slistEl;
    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 slistEl;       // 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;
}
Free 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 slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl 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 slistEl Ptr
  e = New slistEl
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop()
  Dim e As slistEl 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 slistEl 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 slistEl 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 slistEl Ptr Ptr A
Dim As slistEl 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 slistEl 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 slistEl            ' 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 slistEl            ' 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 slistEl          ' 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

 

Rozwiązanie nr 2

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:

 

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.

 

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 Lowdv ; wstępna wartość parametru
K03: dvdv + 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 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 K10 ; sąsiad nieodwiedzony?
K08:     Jeśli D[u] < Low, to LowD[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 Lowtemp ; 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:
L  –  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 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 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:         ncnc + 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  

 

Program

Ważne:

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.

 

Przykładowe dane:

       8 11
0 1 0 2 0 3 0 5
1 4 1 5
2 3
3 6 3 7
4 5
6 7
Lazarus
// 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
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// 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      : PslistEl;          // 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          : PslistEl;
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      : PslistEl;
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.
Code::Blocks
// 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 slistEl
{
  slistEl * next;
  int v;
};

// Zmienne globalne

int n,m,dv;                   // Liczba wierzchołków, krawędzi, numeracja
slistEl ** graf;              // Tablica list sąsiedztwa
int *D;                       // Numery DFS
slistEl * 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;
  slistEl * 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 slistEl;          // 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
  slistEl *p,*r;

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

  graf = new slistEl * [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 slistEl;         // 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 slistEl;         // 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 slistEl;    // 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;
}
Free 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 slistEl
  next As slistEl 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 slistEl Ptr Ptr graf  ' Tablica list sąsiedztwa
Dim Shared As Integer Ptr D         ' Numery DFS
Dim Shared As slistEl 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 slistEl 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 slistEl           ' 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 slistEl Ptr p,r

Open Cons For Input As #1

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

graf = New slistEl 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 slistEl            ' 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 slistEl            ' 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 slistEl       ' 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

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe