Algorytmy i Struktury Danych

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 wybieramy kolejne krawędzie grafu. Wybraną krawędź usuwamy z grafu i ponownie wyznaczamy liczbę spójnych składowych. Jeśli będzie większa od zapamiętanej, to usunięta krawędź jest mostem. W takim przypadku krawędź tę zapamiętujemy, wstawiamy z powrotem do grafu i przechodzimy do następnej krawędzi. Gdy algorytm zakończy swoje działanie, otrzymamy listę krawędzi, które są mostami.

Algorytm naiwny wyszukiwania mostów 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.

Zmienne pomocnicze:

ccn ( n, graf )	–	funkcja zwracająca liczbę spójnych składowych w grafie.
nc	–	liczba spójnych składowych grafu, nc ∈ C.
v, u	–	numery wierzchołków grafu, v, u ∈ 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...K08	przechodzimy przez kolejne wierzchołki grafu
K04:	Dla każdego sąsiada u wierzchołka v : wykonuj kroki K05...K08	przechodzimy przez wszystkich sąsiadów wierzchołka v
K05:	Jeśli u ≤ v, to następny obieg pętli K04	każdą krawędź wybieramy jeden raz
K06:	Usuń krawędź v-u z grafu	wybraną krawędź usuwamy
K07:	Jeśli ccn ( n, graf ) > nc, to dodaj v-u do L	jeśli krawędź jest mostem, to zapamiętujemy ją w L
K08:	Dodaj krawędź v-u do grafu	odtwarzamy krawędź
K09:	Zakończ	mosty 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 mosty i wyświetla je w oknie konsoli. Ponieważ usuwanie krawędzi może być nieco kłopotliwe, zastosowaliśmy tu nieco inną metodę. Otóż wykorzystujemy dodatkową tablicę logiczną VU, której elementy odzwierciedlają wierzchołki. Jeśli dla danej krawędzi v-u oba elementy VU [ v ] i VU [ u ] mają wartość false, to krawędź v-u jest usunięta z grafu. Tablica VU jest dodatkowym parametrem funkcji ccn( ).

Przykładowe dane (spójne składowe zostały pokolorowane w celach testowych ):

17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

Pascal

// Wyszukiwanie mostów w grafie nieskierowanym
// Data: 27.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------

program bridges;

// Typy dla dynamicznej tablicy list sąsiedztwa, stosu i listy mostów
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 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 wierzchołka
      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;         // Numer sąsiada do u
          if( VU [ v ] or 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 mostów

  L := nil;                  // Pusta lista mostów

  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
    p := A [ v ];            // Przeglądamy listę sąsiedztwa wierzchołka v
    while p <> nil do
    begin
      u := p^.v;             // u - numer wierzchołka sąsiedniego w grafie
      if u > v then          // Interesują nas tylko krawędzie w jedną stronę
      begin
        VU [ v ] := false;   // Zaznaczamy krawędź v-u jako usuniętą
        VU [ u ] := false;
        if ccn ( n, A, VU ) > nc then
        begin
          new ( r );         // Znaleziony most dodajemy do listy L
          r^.v := u;
          r^.next := L;
          L := r;
          new ( r );
          r^.v := v;
          r^.next := L;
          L := r;
        end;
        VU [ v ] := true;    // Kasujemy zaznaczenie krawędzi jako usuniętej
        VU [ u ] := true;
      end;
      p := p^.next;
    end;
  end;

  writeln;

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

  v := 0;

  while L <> nil do
  begin
    write ( L^.v, ' ' );
    v := ( v + 1 ) mod 2;
    if v = 0 then writeln;
    p := L;
    L := L^.next;
    dispose ( p );
  end;

  // 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 mostów w grafie nieskierowanym
// Data: 27.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------

#include <iostream>

using namespace std;

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

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( !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 [ v ] || VU [ u ] ) && !C [ u ] )
          {
            S.push ( p->v ); // 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 mostów

  L = NULL;                  // Pusta lista mostów

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

  for( v = 0; v < n; v++ )   // Przechodzimy przez kolejne wierzchołki grafu
  {
    p = A [ v ];             // Przeglądamy listę sąsiedztwa wierzchołka v
    while( p )
    {
      u = p->v;              // u - numer wierzchołka sąsiedniego w grafie
      if( u > v )            // Interesują nas tylko krawędzie w jedną stronę
      {
        VU [ v ] = VU [ u ] = false; // Zaznaczamy krawędź v-u jako usuniętą
        if( ccn ( n, A, VU ) > nc )
        {
          r = new slistEl;   // Znaleziony most dodajemy do listy L
          r->v = u;
          r->next = L;
          L = r;
          r = new slistEl;
          r->v = v;
          r->next = L;
          L = r;
        }
        VU [ v ] = VU [ u ] = true; // Kasujemy zaznaczenie krawędzi jako usuniętej
      }
      p = p->next;
    }
  }

  cout << endl;

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

  v = 0;

  while( L )
  {
    cout << L->v << " ";
    v ^= 1;
    if( !v ) cout << endl;
    p = L;
    L = L->next;
    delete [ ] p;
  }

  // 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 mostów w grafie nieskierowanym
' Data: 27.12.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------------

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

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 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 [ v ] = 1 ) OrElse ( VU [ u ] = 1 ) ) AndAlso ( C [ u ] = 0 ) Then
            S.push ( p->v )  ' 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 mostów

L = 0                        ' Pusta lista mostów

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

For v = 0 To n - 1           ' Przechodzimy przez kolejne wierzchołki grafu
  p = A [ v ]                ' Przeglądamy listę sąsiedztwa wierzchołka v
  While p
    u = p->v                 ' u - numer wierzchołka sąsiedniego w grafie
    If u > v Then            ' Interesują nas tylko krawędzie w jedną stronę
      VU [ v ] = 0           ' Zaznaczamy krawędź v-u jako usuniętą
      VU [ u ] = 0
      If ccn ( n, A, VU ) > nc Then
        r = new slistEl      ' Znaleziony most dodajemy do listy L
        r->v = u
        r->next = L
        L = r
        r = new slistEl
        r->v = v
        r->next = L
        L = r
      End If
      VU [ v ] = 1           ' Kasujemy zaznaczenie krawędzi jako usuniętej
      VU [ u ] = 1
    End If
    p = p->Next
  Wend
Next

Print

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

v = 0

While L
  Print L->v;
  v = ( v + 1 ) Mod 2
  If v = 0 Then Print
  p = L
  L = L->Next
  Delete [ ] p
Wend

' 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:
17 17 0 1 0 2 0 3 1 2 1 14 4 11 4 12 5 6 5 9 6 7 6 8 10 15 11 15 12 15 13 14 13 16 14 16 10 15 6 7 6 8 5 6 5 9 1 14 0 3

Na początek: podrozdziału strony

Teraz zaprezentujemy lepszy algorytm wyszukiwania mostów w grafie nieskierowanym ( w literaturze nosi on nazwę algorytmu R. Tarjana ). Algorytm bazuje na idei drzewa rozpinającego oraz wykorzystuje w specyficzny sposób przejście DFS. Na początek kilka spostrzeżeń, które ten algorytm wykorzystuje.

obrazek

Most nie może być częścią cyklu. Uzasadnienie jest proste i wynika bezpośrednio z definicji mostu. Most jest krawędzią, której usunięcie dzieli składową grafu na dwie oddzielne składowe, czyli takie, dla których nie istnieje droga prowadząca od jednej składowej do drugiej. Lecz cykl w grafie nieskierowanym zawsze można przebyć w obu kierunkach, czyli pomiędzy każdymi dwoma wierzchołkami cyklu zawsze istnieją co najmniej dwie różne drogi dojścia.

Na rysunku obok widzimy fragment grafu. Krawędź łącząca wierzchołki A i B należy do cyklu A–B–C–D–E–A. Gdyby była mostem, to jej usunięcie spowodowałoby, iż od wierzchołka A do B przestałaby istnieć w grafie droga (wierzchołki te znalazłyby się w oddzielnych składowych ). Tymczasem od A do B możemy dojść idąc wzdłuż krawędzi cyklu w drugą stronę. To samo dotyczy dowolnej innej krawędzi należącej do tego cyklu.

Most musi należeć do drzewa rozpinającego. To spostrzeżenie wynika z poprzedniego oraz z własności drzew rozpinających. Drzewo rozpinające jest grafem acyklicznym. Krawędzie grafu, które nie znalazły się w drzewie rozpinającym, są krawędziami tworzącymi cykl, ponieważ prowadzą zawsze do wierzchołków, które wcześniej odwiedziła procedura przejścia grafu DFS lub BFS. Są to tzw. krawędzie wtórne (ang. back edges ). Skoro tak, to krawędzie te nie mogą być mostami, ponieważ należą do cykli. Pozostaje zatem rozważenie tylko tych krawędzi, które są zawarte w drzewie rozpinającym grafu.

Przykładowy graf
obrazek

Drzewo rozpinające grafu
obrazek

Zwróć uwagę, że każda z szarych krawędzi (czyli takich, które nie należą do drzewa rozpinającego) tworzy cykl z krawędziami czarnymi.

W algorytmie Tarjana wykorzystuje się przejście wsteczne drzewa rozpinającego grafu (ang. post-order traversal ). Przejście to wykorzystuje algorytm DFS w sposób następujący:

Oznaczamy bieżący wierzchołek jako odwiedzony.
Przetwarzamy wszystkich nieodwiedzonych jeszcze sąsiadów bieżącego wierzchołka.
Przetwarzamy wierzchołek bieżący.

Przejście DFS wykorzystywane jest do numerowania odwiedzanych wierzchołków oraz do wyznaczania dla każdego z nich dodatkowego parametru Low ( v ). Parametr Low ( v ) dla danego wierzchołka v jest najmniejszą liczbą z numeru wierzchołka v nadanego mu przez DFS, parametrów Low wszystkich jego synów na drzewie rozpinającym oraz numerów DFS wierzchołków połączonych z v za pomocą krawędzi wtórnych (czyli tych, które nie zostały umieszczone na drzewie rozpinającym ). Jeśli napotkamy wierzchołek v, którego numer nadany przez DFS jest równy parametrowi Low ( v ) i wierzchołek ten posiada na drzewie rozpinającym ojca, to krawędź od tego ojca do wierzchołka v jest mostem.

Prześledźmy na prostym przykładzie kolejne kroki algorytmu Tarjana.

	Oto nasz przykładowy graf, w którym mamy znaleźć wszystkie mosty. 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.
	Przejście DFS rozpoczynamy od wierzchołka nr 0 ( może to być dowolny inny wierzchołek grafu ). Wierzchołek ten otrzymuje numer 1 (numery wierzchołków nadane przez DFS będziemy oznaczać kolorem czerwonym ), zostaje oznaczony jako odwiedzony, po czym rekurencyjnie algorytm DFS odwiedza wszystkich nieodwiedzonych jeszcze sąsiadów. Przejście do sąsiada tworzy gałąź w drzewie rozpinającym, którą należy zapamiętać w osobnej strukturze danych.
	Zatem z wierzchołka nr 0 przechodzimy do wierzchołka nr 2. Oznaczamy go jako odwiedzonego i numerujemy liczbą 2. Krawędź 0–1 staje się krawędzią drzewa rozpinającego. Odwiedzamy rekurencyjnie wszystkich sąsiadów wierzchołka nr 1.
	Przechodzimy do wierzchołka nr 2. Oznaczamy go jako odwiedzonego i numerujemy liczbą 3. Krawędź 1–2 jest dołączana do drzewa rozpinającego. Ponieważ wszyscy sąsiedzi wierzchołka nr 2 zostali już odwiedzeni, to przechodzimy do przetwarzania samego wierzchołka nr 2. Polega ono na wyznaczeniu parametru Low dla tego wierzchołka. Będzie to najmniejsza wartość z 3 i 1, czyli 1 ( 3 – numer wierzchołka nadany przez DFS, 1 – numer wierzchołka połączonego krawędzią wtórną 2 – 0 ). Ponieważ Low ( 2 ) = 1 jest różne od numeru 3, który wierzchołkowi nadało DFS, zatem krawędź 1–2 (ojciec – syn na drzewie rozpinającym) nie jest mostem.. Wracamy z powrotem do wierzchołka nr 1, z którego tutaj przyszliśmy.
	Z wierzchołka nr 1 przechodzimy do kolejnego nieodwiedzonego sąsiada, czyli do wierzchołka nr 4. Wierzchołek nr 4 oznaczamy jako odwiedzony, nadajemy mu numer 4. Krawędź 1–4 zostaje dodana do drzewa rozpinającego. Wierzchołek nr 4 posiada dwóch nieodwiedzonych sąsiadów: 3 i 5.
	Z wierzchołka nr 4 przechodzimy do wierzchołka nr 3. Oznaczamy go jako odwiedzony i nadajemy mu numer 5. Krawędź 4–5 trafia do drzewa rozpinającego. Wierzchołek nr 3 posiada nieodwiedzonego jeszcze sąsiada nr 5.
	Z wierzchołka nr 3 przechodzimy do wierzchołka nr 5. Oznaczamy go jako odwiedzony i nadajemy mu numer 6. Krawędź 3–5 dołączamy do drzewa rozpinającego. Wierzchołek nr 5 nie posiada więcej nieodwiedzonych sąsiadów. Zatem wyliczamy dla niego parametr Low jako mniejszą liczbę z 6 ( numer nadany wierzchołkowi 5 przez DFS) i 4 (numer DFS wierzchołka 4, do którego prowadzi krawędź wtórna ). Low ( 5 ) = min ( 6, 4 ) = 4 Ponieważ parametr Low ma dla tego wierzchołka wartość różną od numeru nadanego przez DFS, krawędź 3–5 nie jest mostem. Przetwarzanie wierzchołka nr 5 jest zakończone, wracamy do wierzchołka nr 3, z którego przyszliśmy.
	Jesteśmy w wierzchołku nr 3. Wszyscy sąsiedzi zostali odwiedzeni. Wyliczamy parametr Low ( 3 ) jako najmniejszą liczbę z 5 (numer DFS wierzchołka 3) i 4 (parametr Low wierzchołka nr 6, który jest synem ). Low ( 3 ) = min ( 5, 4 ) = 4 Ponieważ Low ( 3 ) = 4 jest różne od numeru DFS równego 5 dla wierzchołka nr 3, krawędź 4–3 nie jest mostem. Wracamy do wierzchołka nr 4.
	Jesteśmy w wierzchołku nr 4. Wszyscy sąsiedzi wierzchołka nr 4 są odwiedzeni. Obliczamy Low ( 4 ) jako najmniejszą liczbę z 4 (numer DFS wierzchołka nr 4 ), 4 (parametr Low ( 3 ) = 4, ponieważ wierzchołek nr 3 jest synem wierzchołka nr 4 na drzewie rozpinającym) oraz 6 (numer DFS wierzchołka nr 5, który łączy się z nim krawędzią wtórną ). Low ( 4 ) = min ( 4, 4, 6 ) = 4 Ponieważ parametr Low jest równy numerowi DFS, to krawędź 1–4 jest mostem. Wracamy do wierzchołka nr 1.
	Jesteśmy w wierzchołku nr 1. Wszyscy jego sąsiedzi są odwiedzeni. Obliczamy Low ( 1 ) jako najmniejszą liczbę z 2 (numer DFS wierzchołka 1) i 1 (parametr Low ( 2 ) = 1, ponieważ wierzchołek nr 2 jest synem na drzewie rozpinającym ). Low ( 1 ) = min ( 2, 1 ) = 1 Parametr Low różni się od numeru DFS, zatem krawędź 0–1 nie jest mostem.
	Jesteśmy w wierzchołku startowym nr 0. Wszyscy sąsiedzi zostali już odwiedzeni. Obliczamy Low ( 0 ) jako najmniejszą liczbę z 1 (numer DFS wierzchołka 0 ), 1 (parametr Low ( 1 ), ponieważ wierzchołek nr 1 jest synem na drzewie rozpinającym) i 3 ( numer DFS wierzchołka 2, który łączy się krawędzią wtórną ). Low ( 0 ) = min ( 1, 1, 3 ) = 1 Mamy równość parametru Low ( 0 ) z numerem DFS. Jednakże wierzchołek nr 0 nie posiada ojca na drzewie rozpinającym, zatem nie istnieje łącząca go z nim krawędź-most. Cały graf został przetworzony. Algorytm Tarjana kończy się.

Zwróć uwagę, że wszystkie mosty w danej spójnej składowej grafu zostaną znalezione w jednym przejściu DFS. Zatem otrzymujemy algorytm działający w czasie liniowym.

Algorytm Tarjana wyszukiwania mostów w grafie nieskierowanym

Funkcja rekurencyjna DFSb ( v, vf, graf, D, cv, 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.
cv	–	referencja do zmiennej zewnętrznej przechowującej numery wierzchołków. Przy pierwszym wywołaniu zmienna powinna zawierać 1. cv ∈ C.
L	–	lista mostów. Przechowuje numery wierzchołka startowego i końcowego krawędzi-mostu.

Wyjście:

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

Zmienne pomocnicze:

Low	–	wartość parametru Low dla bieżącego wierzchołka, Low ∈ C.
temp	–	chwilowo przechowuje wynik wywołania rekurencyjnego, t ∈ C.

Lista kroków:

K01:	D [ v ] ← cv	numerujemy wierzchołek
K02	Low ← cv	wstępna wartość parametru
K03:	cv ← cv + 1	kolejny wierzchołek będzie miał numer o 1 większy
K04:	Dla każdego sąsiada u wierzchołka v : wykonuj kroki K05...K10	przeglądamy wszystkich sąsiadów wierzchołka bieżącego
K05:	Jeśli u = vf, to następny obieg pętli K04	pomijamy ojca na drzewie rozpinającym
K06:	Jeśli D [ u ] = 0, to idź do kroku K09	sąsiad nieodwiedzony?
K07:	Jeśli D [ u ] < Low, to Low ← D [ u ]	odwiedzony, krawędź wtórna. Modyfikujemy parametr Low
K08:	Następny obieg pętli K04
K09:	temp ← DFSb ( u, v, graf, T, D, cv, L )	rekurencyjne wywołanie funkcji
K10:	Jeśli temp < Low, to Low ← temp	modyfikujemy parametr Low
K11:	Jeśli ( vf > -1 ) ( Low = D [ v ] ), to dodaj krawędź vf, v do listy L	sąsiedzi odwiedzeni. Sprawdzamy warunek mostu
K12:	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 L zawiera krawędzie będące mostami

Zmienne pomocnicze:

cv	–	przechowuje numery wierzchołków dla DFS, cv ∈ C.
D	–	dynamiczna tablica dla numerów wierzchołków nadawanych przez DFS. Elementy są liczbami całkowitymi.
L	–	lista par wierzchołków, które są połączone mostem.
i	–	numery wierzchołków w grafie, i ∈ C.

Lista kroków:

K01	Twórz n elementową tablicę D
K02:	Zeruj tablicę D
K03:	Twórz pustą listę L
K04:	Dla i = 0, 1, ..., n - 1: wykonuj kroki K05...K07
K05:	Jeśli D [ i ] > 0, to następny obieg pętli K04	szukamy nieodwiedzonych jeszcze wierzchołków
K06:	cv ← 1	numer DFS pierwszego wierzchołka
K07:	DFSb ( i, -1, graf, D, cv, L )	szukamy mostów
K08:	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 mosty i wyświetla je w oknie konsoli. Aby uprościć funkcję rekurencyjną DFSb( ), większość jej parametrów została zrealizowana jako zmienne globalne.

Przykładowe dane (spójne składowe zostały pokolorowane w celach testowych ):

17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

Pascal

// Wyszukiwanie mostów w grafie nieskierowanym
// Data: 28.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------

program bridges;

// Typy dla dynamicznej tablicy list sąsiedztwa i listy mostów
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// Zmienne globalne

var
  n, m, cv : 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 mosty
// v  - numer bieżącego wierzchołka
// vf - ojciec bieżącego wierzchołka na drzewie rozpinającym
// Reszta parametrów to zmienne globalne
//----------------------------------------------------------
function DFSb ( v, vf : integer ) : integer;
var
  Low, temp, u : integer;
  p          : PslistEl;
begin
  D [ v ] := cv;             // Numerujemy wierzchołek
  Low  := cv;                // Wstępna wartość parametru Low
  inc ( cv );                // Następny numer wierzchołka

  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 := DFSb ( u, v );    // rekurencyjnie odwiedzamy go
        if temp < Low then Low := temp;
      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. Teraz robimy test na most

  if( vf > -1 ) and ( Low = D [ v ] ) then
  begin
    new ( p );               // Mamy most. Dodajemy go do listy L
    p^.v := v;
    p^.next := L;
    L := p;
    new ( p );
    p^.v := vf;
    p^.next := L;
    L := p;
  end;

  DFSb := Low;               // Wynik
end;

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

var
  i, u, v : integer;         // Numery wierzchołków
  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 mostów

  for i := 0 to n - 1 do
    if D [ i ] = 0 then      // Szukamy nieodwiedzonego wierzchołka
    begin
      cv   := 1;             // Początek numeracji DFS
      DFSb ( i, -1 );        // Szukamy mostów
    end;

  writeln;

  // Wypisujemy znalezione mosty

  v := 0;

  while L <> nil do
  begin
    write ( L^.v, ' ' );
    v := ( v + 1 ) mod 2;
    if v = 0 then writeln;
    p := L;
    L := L^.next;
    dispose ( p );
  end;

  // 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 mostów w grafie nieskierowanym
// Data: 28.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------

#include <iostream>

using namespace std;

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

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

// Zmienne globalne

int n, m, cv;                 // 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 mosty
// v  - numer bieżącego wierzchołka
// vf - ojciec bieżącego wierzchołka na drzewie rozpinającym
// Reszta parametrów to zmienne globalne
//----------------------------------------------------------
int DFSb ( int v, int vf )
{
  int Low, temp, u;
  slistEl * p;

  // Numerujemy wierzchołek, ustalamy wstępną wartość Low oraz zwiększamy numerację

  D [ v ] = Low = cv++;

  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 = DFSb ( u, v ); // rekurencyjnie odwiedzamy go
        if( temp < Low ) Low = temp;
      }
      else if( D [ u ] < Low ) Low = D [ u ];
    }
  }

  // Wszyscy sąsiedzi zostali odwiedzeni. Teraz robimy test na most

  if( ( vf > -1 ) && ( Low == D [ v ] ) )
  {
    p = new slistEl;       // Mamy most. Dodajemy go do listy L
    p->v = v;
    p->next = L;
    L = p;
    p = new slistEl;
    p->v = vf;
    p->next = L;
    L = p;
  }

  return Low;              // Wynik
}

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

int main( )
{
  int i, u, v;             // Numery wierzchołków
  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 mostów

  for( i = 0; i < n; i++ )
    if( !D [ i ] )          // Szukamy nieodwiedzonego wierzchołka
    {
      cv   = 1;             // Początek numeracji DFS
      DFSb ( i, -1 );       // Szukamy mostów
    }

  cout << endl;

  // Wypisujemy znalezione mosty

  v = 0;

  while( L )
  {
    cout << L->v << " ";
    v ^= 1;
    if( !v ) cout << endl;
    p = L;
    L = L->next;
    delete p;
  }

  // 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 mostów w grafie nieskierowanym
' Data: 28.12.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------------

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

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer n, m, cv ' 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 mosty
' v  - numer bieżącego wierzchołka
' vf - ojciec bieżącego wierzchołka na drzewie rozpinającym
' Reszta parametrów to zmienne globalne
'---------------------------------------
Function DFSb ( ByVal v As Integer, ByVal vf As Integer ) As Integer

  Dim As Integer Low, temp, u
  Dim As slistEl Ptr p

  ' Numerujemy wierzchołek, ustalamy wstępną wartość Low oraz zwiększamy numerację

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

  p = graf [ v ] 
  While p                    ' Przeglądamy listę sąsiadów
    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 = DFSb ( u, v ) ' rekurencyjnie odwiedzamy go
        If temp < Low Then Low = temp
      Else
        If D [ u ] < Low Then Low = D [ u ] 
      End If
    End If 
    p = p->Next
  Wend

  ' Wszyscy sąsiedzi zostali odwiedzeni. Teraz robimy test na most

  if( vf > -1 ) AndAlso ( Low = D [ v ] ) Then
    p = new slistEl          ' Mamy most. Dodajemy go do listy L
    p->v = v
    p->next = L
    L = p
    p = new slistEl
    p->v = vf
    p->next = L
    L = p
  End If

  return Low                 ' Wynik
End Function

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

Dim As Integer i, u, v       ' Numery wierzchołków
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 mostów

For i = 0 To n - 1
  If D [ i ] = 0 Then       ' Szukamy nieodwiedzonego wierzchołka
    cv   =  1               ' Początek numeracji DFS
    DFSb ( i, -1 )          ' Szukamy mostów
  End If
Next

Print 

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

v = 0

While L
  print L->v;
  v = ( v + 1 ) Mod 2
  If v = 0 Then Print
  p = L
  L = L->Next
  Delete [ ] p
Wend

' 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:
17 17 0 1 0 2 0 3 1 2 1 14 4 11 4 12 5 6 5 9 6 7 6 8 10 15 11 15 12 15 13 14 13 16 14 16 5 6 6 7 6 8 5 9 15 10 1 14 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 mostów w grafie

Problem

Rozwiązanie nr 1

Algorytm naiwny wyszukiwania mostów w grafie nieskierowanym

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm Tarjana wyszukiwania mostów w grafie nieskierowanym

Funkcja rekurencyjna DFSb ( v, vf, graf, D, cv, L )

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Algorytm główny

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy