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:

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, 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, ; przechodzimy przez
     wykonuj kroki K04…K08 ; kolejne wierzchołki grafu
K04:   Dla każdego sąsiada u wierzchołka v: ; przechodzimy przez
       wykonuj kroki K05…K08 ; wszystkich sąsiadów wierzchołka v
K05:     Jeśli u ≤ v, ; każdą krawędź wybieramy jeden raz
         to następny obieg pętli K04
K06:       Usuń krawędź v-u z grafu ; wybraną krawędź usuwamy
K07:       Jeśli ccn(n, graf) > nc, ; jeśli krawędź jest mostem,
           to dodaj v-u do L ; 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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Definicja typu obiektowego
// Stack
//--------------------------
Stack = object
  private
    // lista przechowująca stos
    S : PSLel;
  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
  if S = nil then
    top := -2
  else
    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
  // Tworzymy pusty stos
  S.init;
  // Tworzymy tablicę spójnych
  // składowych
  SetLength(C, n);
  for i := 0 to n-1 do
    // Zerujemy tablicę spójnych
    // składowych
    C[i] := 0;
  // Zerujemy licznik spójnych
  // składowych
  cc := 0;
  for i := 0 to n-1 do
    // Szukamy nieodwiedzonego
    // jeszcze wierzchołka
    if C[i] = 0 then
    begin
      // Zwiększamy licznik
      // składowych
      inc(cc);
      // Na stosie umieszczamy
      // numer bieżącego
      // wierzchołka
      S.push(i);
      // Wierzchołek numerujemy
      // i oznaczamy jako
      // odwiedzony
      C[i] := cc;
      // Przechodzimy graf
      // algorytmem DFS
      while not S.empty do
      begin
        // Pobieramy wierzchołek
        v := S.top;
        // Usuwamy go ze stosu
        S.pop;
        // Przeglądamy sąsiadów
        // wierzchołka v
        p := graf[v];
        while p <> nil do
        begin
          // Numer sąsiada do u
          u := p^.v;
          if (VU[v] or VU[u]) and
             (C [u] = 0) then
          begin
            // Na stos idą sąsiedzi
            // nieodwiedzeni
            S.push(u);
            // i ponumerowani
            C[u] := cc;
          end;
          p := p^.next;
        end;
      end;
    end;
  // Usuwamy tablicę C
  SetLength(C, 0);
  // Usuwamy stos
  S.destroy;
  // Zwracamy wynik
  ccn := cc;
end;

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

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

begin
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(A, n);
  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
    // Wierzchołki tworzące krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako w
    p^.v := u;
    // Dodajemy go na początek
    // listy A[v]
    p^.next := A[v];
    A[v] := p;
    // To samo dla krawędzi
    // w drugą stronę
    new(p);
    p^.v := v;
    p^.next := A[u];
    A[u] := p;
  end;
  // Algorytm znajdowania mostów
  // ---------------------------
  // Pusta lista mostów
  L := nil;
  // Zapamiętujemy liczbę spójnych
  // składowych
  nc := ccn(n, A, VU);
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for v := 0 to n-1 do
  begin
    // Przeglądamy listę sąsiedztwa
    // wierzchołka v
    p := A[v];
    while p <> nil do
    begin
      // u-numer wierzchołka
      // sąsiedniego w grafie
      u := p^.v;
      // Interesują nas tylko
      // krawędzie w jedną stronę
      if u > v then
      begin
        // Zaznaczamy krawędź v-u
        // jako usuniętą
        VU[v] := false;
        VU[u] := false;
        if ccn(n, A, VU) > nc then
        begin
          // Znaleziony most
          // dodajemy do listy L
          new(r);
          r^.v := u;
          r^.next := L;
          L := r;
          new(r);
          r^.v := v;
          r^.next := L;
          L := r;
        end;
        // Kasujemy zaznaczenie
        // krawędzi jako usuniętej
        VU[v] := true;
        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 SLel
{
  SLel * next;
  int v;
};

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

  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 = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

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

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

// 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;

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

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

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

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy zmienne dynamiczne
  // ---------------------------
  // Krawędzie aktywne
  VU = new bool [n];
  // Tablica list sąsiedztwa
  A  = new SLel * [n];
  // Tablicę wypełniamy pustymi
  // listami
  for(i = 0; i < n; i++)
  {
    A[i] = nullptr;
    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 mostów
  //----------------------------
  // Pusta lista mostów
  L = nullptr;
  // Zapamiętujemy liczbę
  // spójnych składowych
  nc = ccn(n, A, VU);
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for(v = 0; v < n; v++)
  {
    // Przeglądamy listę
    // sąsiedztwa wierzchołka v
    p = A[v];
    while(p)
    {
      // u-numer wierzchołka
      // sąsiedniego w grafie
      u = p->v;
      // Interesują nas tylko
      // krawędzie w jedną
      // stronę
      if(u > v)
      {
        // Zaznaczamy krawędź
        // v-u jako usuniętą
        VU[v] = VU[u] = false;
        if(ccn(n, A, VU) > nc)
        {
          // Znaleziony most
          // dodajemy do listy L
          r = new SLel;
          r->v = u;
          r->next = L;
          L = r;
          r = new SLel;
          r->v = v;
          r->next = L;
          L = r;
        }
        // Kasujemy zaznaczenie
        // krawędzi jako
        // usuniętej
        VU[v] = VU[u] = true;
      }
      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 SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr
  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
  If S <> 0 Then
    top = S->v
  Else
    top = -2
  End If
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

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

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
' Odczytujemy liczbę
' wierzchołków i krawędzi
Input #1, n, m 
' Tworzymy tablice dynamiczne
A = New SLel Ptr [n]
' Krawędzie aktywne
VU = New Byte [n]
' Tablicę A wypełniamy pustymi listami
For i = 0 To n-1
  A[i] = 0
  VU[i] = 1
Next
' Odczytujemy kolejne definicje krawędzi.
For i = 0 To m-1
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako u
  p->v = u
  ' Dodajemy go na początek listy A[v]
  p->next = A[v]
  A[v] = p
  ' To samo dla krawędzi w drugą stronę
  p = new SLel
  p->v = v
  p->next = A[u]
  A[u] = p
Next
' Algorytm znajdowania mostów
'----------------------------
' Pusta lista mostów
L = 0
' Zapamiętujemy liczbę spójnych składowych
nc = ccn(n, A, VU)
' Przechodzimy przez kolejne
' wierzchołki grafu
For v = 0 To n-1
  ' Przeglądamy listę sąsiedztwa
  ' wierzchołka v
  p = A[v]
  While p <> 0
    ' u-numer wierzchołka
    ' sąsiedniego w grafie
    u = p->v
    ' Interesują nas tylko
    ' krawędzie w jedną stronę
    If u > v Then
      ' Zaznaczamy krawędź v-u
      ' jako usuniętą
      VU[v] = 0
      VU[u] = 0
      If ccn(n, A, VU) > nc Then
        ' Znaleziony most dodajemy
        ' do listy L
        r = new SLel
        r->v = u
        r->next = L
        L = r
        r = new SLel
        r->v = v
        r->next = L
        L = r
      End If
      ' Kasujemy zaznaczenie krawędzi
      ' jako usuniętej
      VU[v] = 1
      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

Python (dodatek)

# Wyszukiwanie mostów
# w grafie nieskierowanym
# Data: 10.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasy dla dynamicznej tablicy
# list sąsiedztwa, stosu i listy mostów
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None


    # Destruktor
    def __del__(self):
        while self.s:
            self.pop()


    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu
    def top(self):
        if self.s:
            return self.s.v
        else:
            return -2


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# 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
#------------------------------------------
def ccn(n, graf, vu):
    s = Stack()
    # Tworzymy tablicę spójnych składowych
    c = [0] * n
    # Zerujemy licznik spójnych składowych
    cc = 0
    for i in range(n):
        # Szukamy nieodwiedzonego
        # jeszcze wierzchołka
        if not c[i]:
            # Zwiększamy licznik składowych
            cc += 1
            # Na stosie umieszczamy numer
            # bieżącego węzła
            s.push(i)
            # Wierzchołek numerujemy
            # i oznaczamy jako odwiedzony
            c[i] = cc
            # Przechodzimy graf algorytmem DFS
            while not s.empty():
                # Pobieramy wierzchołek
                v = s.top()
                # Usuwamy go ze stosu
                s.pop()
                # Przeglądamy sąsiadów
                # wierzchołka v
                p = graf[v]
                while p:
                    u = p.v
                    if (vu[v] or vu[u]) and \
                        not c[u]:
                        # Na stos idą sąsiedzi
                        # nieodwiedzeni
                        s.push(p.v)
                        # Na stos idą sąsiedzi
                        # nieodwiedzeni
                        # i ponumerowani
                        c[u] = cc
                    p = p.next
    # Usuwamy tablicę C
    del c
    # Zwracamy wynik
    return cc


# **********************
# *** Program główny ***
# **********************

# Odczytujemy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
a = [None] * n
# Krawędzie aktywne
vu = [True] * n
# Odczytujemy kolejne definicje krawędzi
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako u
    p.v = u
    # Dodajemy go na początek listy A[v]
    p.next = a[v]
    a[v] = p
    # To samo dla krawędzi w drugą stronę
    p = SLel()
    p.v = v
    p.next = a[u]
    a[u] = p
# Algorytm znajdowania mostów
#----------------------------
# Pusta lista mostów
blst = None
# Zapamiętujemy liczbę spójnych składowych
nc = ccn(n, a, vu)
# Przechodzimy przez kolejne
# wierzchołki grafu
for v in range(n):
    # Przeglądamy listę sąsiedztwa
    # wierzchołka v
    p = a[v]
    while p:
        # u-numer wierzchołka
        # sąsiedniego w grafie
        u = p.v
        # Interesują nas tylko
        # krawędzie w jedną stronę
        if u > v:
            # Zaznaczamy krawędź v-u
            # jako usuniętą
            vu[v] = False
            vu[u] = False
            if ccn(n, a, vu) > nc:
                # Znaleziony most dodajemy
                # do listy mostów blst
                r = SLel()
                r.v = u
                r.next = blst
                blst = r
                r = SLel()
                r.v = v
                r.next = blst
                blst = r
            # Kasujemy zaznaczenie krawędzi
            # jako usuniętej
            vu[v] = True
            vu[u] = True
        p = p.next
print()
# Wypisujemy znalezione mosty,
# jednocześnie usuwając listę L
v = 0
while blst:
    print(blst.v, end=" ")
    v = (v+1) % 2
    if not v: print()
    blst = blst.next
# Usuwamy dynamiczne struktury danych
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a, vu

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

do podrozdziału do 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.

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.

Elementy pomocnicze:

Low : wartość parametru Low dla bieżącego wierzchołka; Low ∈ C.
temp : chwilowo przechowuje wynik wywołania rekurencyjnego; temp ∈ 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: ; przeglądamy wszystkich
     wykonuj kroki K05…K10 ; sąsiadów wierzchołka bieżącego
K05:   Jeśli u = vf, ; pomijamy ojca na drzewie rozpinającym
       to następny obieg pętli K04
K06:   Jeśli D[u] = 0, ; sąsiad nieodwiedzony?
       to idź do kroku K09
K07:   Jeśli D[u] < Low, ; odwiedzony, krawędź wtórna.
       to Low ← D[u] ; 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, ; modyfikujemy parametr Low
       to Low ← temp
K11: Jeśli (vf > -1)  (Low = D[v]), ; sąsiedzi odwiedzeni.
     to dodaj krawędź vf, v do listy L ; 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.

Elementy 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, ; szukamy nieodwiedzonych jeszcze wierzchołków
       to następny obieg pętli K04
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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

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

// 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 : PSLel;
begin
  // Numerujemy wierzchołek
  D[v] := cv;
  // Wstępna wartość
  // parametru Low
  Low := cv;
  // Następny numer
  // wierzchołka
  inc(cv);
  // Przeglądamy
  // listę sąsiadów
  p := graf[v];
  while p <> nil do
  begin
    // u-numer
    // wierzchołka sąsiada
    u := p^.v;
    // u nie może być
    // ojcem v
    if u <> vf then
    begin
      // Jeśli sąsiad u
      // nie był odwiedzany,
      if D[u] = 0 then
      begin
        // rekurencyjnie
        // odwiedzamy go
        temp := DFSb(u, v);
        if temp < Low then
          Low := temp;
      end
      else if D[u] < Low then
             Low := D[u];
    end;
    // Następny wierzchołek
    // na liście
    p := p^.next;
  end;
  // Wszyscy sąsiedzi zostali
  // odwiedzeni. Teraz robimy
  // test na most
  if (vf > -1) and
     (Low = D[v]) then
  begin
    // Mamy most. Dodajemy go
    // do listy L
    new(p);
    p^.v := v;
    p^.next := L;
    L := p;
    new(p);
    p^.v := vf;
    p^.next := L;
    L := p;
  end;
  // Wynik
  DFSb := Low;
end;

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

var
  // Numery wierzchołków
  i, u, v : integer;
  p, r   : PSLel;
begin
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy zmienne
  // dynamiczne
  SetLength(graf, n);
  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
    // Wierzchołki tworzące
    // krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako w
    p^.v := u;
    // Dodajemy go na początek
    // listy graf[v]
    p^.next := graf[v];
    graf[v] := p;
    // To samo dla krawędzi
    // w drugą stronę
    new(p);
    p^.v := v;
    p^.next := graf[u];
    graf[u] := p;
  end;
  // Szukamy mostów
  for i := 0 to n-1 do
    // Szukamy nieodwiedzonego
    // wierzchołka
    if D[i] = 0 then
    begin
      // Początek numeracji DFS
      cv := 1;
      // Szukamy mostów
      DFSb(i, -1);
    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 SLel
{
  SLel * next;
  int v;
};

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

// 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;
  SLel * p;

  // Numerujemy wierzchołek,
  // ustalamy wstępną wartość Low
  // oraz zwiększamy numerację
  D[v] = Low = cv++;
  // Przeglądamy listę sąsiadów
  for(p = graf[v]; p; p = p->next)
  {
    // u-numer wierzchołka
    // sąsiada
    u = p->v;
    // u nie może być ojcem v
    if(u != vf)
    {
      // Jeśli sąsiad u nie był
      // odwiedzany, to
      if(!D[u])
      {
        // rekurencyjnie
        // odwiedzamy go
        temp = DFSb(u, v);
        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]))
  {
    // Mamy most. Dodajemy go
    // do listy L
    p = new SLel;
    p->v = v;
    p->next = L;
    L = p;
    p = new SLel;
    p->v = vf;
    p->next = L;
    L = p;
  }
  // Wynik
  return Low;
}

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

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

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy zmienne
  // dynamiczne
  graf = new SLel * [n];
  D = new int [n];
  L = nullptr;
  for(i = 0; i < n; i++)
  {
    graf[i] = nullptr;
    D[i] = 0;
  }
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołki tworzące
    // krawędź
    cin >> v >> u;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako u
    p->v = u;
    // Dodajemy go na początek
    // listy graf[v]
    p->next = graf[v];
    graf[v] = p;
    // To samo dla krawędzi
    // w drugą stronę
    p = new SLel;
    p->v = v;
    p->next = graf[u];
    graf[u] = p;
  }
  // Szukamy mostów
  for(i = 0; i < n; i++)
    // Szukamy nieodwiedzonego
    // wierzchołka
    if(!D[i])
    {
      // Początek numeracji DFS
      cv = 1;
      // Szukamy mostów
      DFSb(i, -1);
    }
  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 SLel
  next As SLel Ptr
  v As Integer
End Type

' Zmienne globalne

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

' 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 SLel Ptr p

  ' Numerujemy wierzchołek,
  ' ustalamy wstępną wartość Low
  ' oraz zwiększamy numerację
  D[v] = cv: Low = cv: cv += 1
  p = graf[v]
  ' Przeglądamy listę sąsiadów
  While p <> 0
    ' u-numer wierzchołka sąsiada
    u = p->v
    ' u nie może być ojcem v
    If u <> vf Then
      ' Jeśli sąsiad u nie był
      ' odwiedzany,
      If D[u] = 0 Then
        ' rekurencyjnie
        ' odwiedzamy go
        temp = DFSb(u, v)
        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
    ' Mamy most. Dodajemy go
    ' do listy L
    p = new SLel
    p->v = v
    p->next = L
    L = p
    p = new SLel
    p->v = vf
    p->next = L
    L = p
  End If
  ' Wynik
  Return Low
End Function

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

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

Open Cons For Input As #1
' Odczytujemy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy zmienne dynamiczne
graf = New SLel Ptr [n]
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
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako u
  p->v = u
  ' Dodajemy go na początek
  ' listy graf[v]
  p->next = graf[v]
  graf[v] = p
  ' To samo dla krawędzi
  ' w drugą stronę
  p = new SLel
  p->v = v
  p->next = graf[u]
  graf[u] = p
Next
Close #1
' Szukamy mostów
For i = 0 To n-1
  ' Szukamy nieodwiedzonego
  ' wierzchołka
  If D[i] = 0 Then
    ' Początek numeracji DFS
    cv =  1
    ' Szukamy mostów
    DFSb(i, -1)
  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 <> 0
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] D
Delete [] graf
End

Python (dodatek)

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

# Klasa dla dynamicznej tablicy
# list sąsiedztwa i listy mostów
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# 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
#----------------------------------
def dfsb(v, vf):
    global d, cv, graf, lst
    # Numerujemy wierzchołek,
    # ustalamy wstępną wartość Low
    # oraz zwiększamy numerację
    d[v] = cv
    low = cv
    cv += 1
    p = graf[v]
    # Przeglądamy listę sąsiadów
    while p:
        # u - numer wierzchołka
        #     sąsiada
        u = p.v
        # u nie może być ojcem v
        if u != vf:
            # Jeśli sąsiad u
            # nie był odwiedzany,
            if not d[u]:
                # rekurencyjnie
                # odwiedzamy go
                temp = dfsb(u, v)
                if temp < low:
                    low = temp
            else:
                if d[u] < low:
                    low = d[u]
        p = p.next
    # Wszyscy sąsiedzi zostali
    # odwiedzeni. Teraz robimy
    # test na most
    if (vf > -1) and (low == d[v]):
        # Mamy most. Dodajemy go
        # do listy lst
        p = SLel()
        p.v = v
        p.next = lst
        lst = p
        p = SLel()
        p.v = vf
        p.next = lst
        lst = p
    # Wynik
    return low


# **********************
# *** Program główny ***
# **********************

# Odczytujemy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy zmienne dynamiczne
graf = [None] * n
d = [0] * n
lst = None
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako u
    p.v = u
    # Dodajemy go na początek
    # listy graf[v]
    p.next = graf[v]
    graf[v] = p
    # To samo dla krawędzi
    # w drugą stronę
    p = SLel()
    p.v = v
    p.next = graf[u]
    graf[u] = p
# Szukamy mostów
for i in range(n):
    # Szukamy nieodwiedzonego
    # wierzchołka
    if not d[i]:
        # Początek numeracji DFS
        cv = 1
        # Szukamy mostów
        dfsb(i, -1)
print()
# Wypisujemy znalezione mosty,
# jednocześnie usuwając listę lst
v = 0
while lst:
    print(lst.v, end=" ")
    v = (v+1) % 2
    if not v:
        print()
    lst = lst.next
# Usuwamy dynamiczne
# struktury danych
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del d, graf

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

do podrozdziału do 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:

Elementy 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:

Elementy pomocnicze:

Lista kroków:

Algorytm główny

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy