Znajdowanie silnie spójnych składowych 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 naiwne
Algorytm Kosaraju
Algorytm Tarjana

Problem

Dla danego grafu skierowanego wyznaczyć wszystkie silnie spójne składowe.



Silnie spójna składowa (ang. strongly connected component) jest maksymalnym podgrafem, w którym istnieją ścieżki pomiędzy każdymi dwoma wierzchołkami. Jeśli podgraf ten obejmuje wszystkie wierzchołki grafu, to mówimy, że dany graf skierowany jest silnie spójny (ang. strongly connected digraph) (w grafach nieskierowanych każdy graf spójny jest również silnie spójny).

 

        
Silnie spójna składowa
(1,2,4,5,8)
  Silnie spójny graf skierowany

 

Silnie spójna składowa może się redukować do jednego wierzchołka, jeśli nie jest on połączony obustronnie z żadnym innym wierzchołkiem grafu. Na rysunku powyżej takimi składowymi są (0) (3) (6) i (7).

 

Rozwiązanie naiwne

Rozwiązanie naiwne opiera się bezpośrednio na definicji silnie spójnej składowej. Jest ono bardzo nieefektywne i podajemy je tylko ze względów dydaktycznych. Lepsze algorytmy znajdowania silnie spójnych składowych prezentowane są w dalszej części artykułu.

 

Tworzymy tablicę n elementową C, której komórki będą odpowiadały n wierzchołkom grafu. Będziemy w niej umieszczać numery silnie spójnych składowych, do których należą poszczególne wierzchołki. Tablicę C wstępnie zerujemy. Umawiamy się przy tym, iż numer 0 nie oznacza żadnej spójnej składowej.

Do numeracji spójnych składowych będziemy używali zmiennej cn. Inicjujemy jej wartość na 0.

Przechodzimy w pętli wierzchołki grafu od pierwszego do przedostatniego. Szukamy wierzchołka startowego v, dla którego C[v] = 0. Gdy go znajdziemy, zwiększamy cn o 1, do C[v] wprowadzamy cn i rozpoczynamy przejście DFS od tego wierzchołka. W każdym odwiedzonym wierzchołku u uruchamiamy drugie przejście DFS, które sprawdza, czy istnieje ścieżka od wierzchołka u do wierzchołka startowego v. Jeśli tak, to do C[u] zapisujemy cn.

Po przetworzeniu wszystkich wierzchołków w tablicy C otrzymamy informację o tym, które wierzchołki grafu należą do poszczególnych spójnych składowych. Dodatkowo cn określa liczbę tych silnie spójnych składowych.

 

Algorytm naiwny wyszukiwania silnie spójnych składowych w grafie skierowanym

Algorytm przejścia DFSback(u,v,n,graf)
Wejście
u  –  wierzchołek bieżący, u C
v  –  wierzchołek startowy, u C
n  –  liczba wierzchołków w grafie, n C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
Zwraca true, jeśli istnieje ścieżka z u do v. W przeciwnym razie zwraca false.
Elementy pomocnicze:
x,y  –  wierzchołki, x,y C
S  –  pusty stos wierzchołków
visited  –  n elementowa logiczna tablica odwiedzin
Lista kroków:
K01: Utwórz n elementową tablicę visited  
K02: Ustaw elementy tablicy visited na false  
K03: S.push(u) ; umieszczamy wierzchołek startowy na stosie
K04: visited[u] ← true ; oznaczamy go jako odwiedzony
K05: Dopóki S.empty() = false, wykonuj K06...K12 ; przejście DFS
K06:     xS.top() ; pobieramy ze stosu wierzchołek
K07:     S.pop() ; pobrany wierzchołek usuwamy ze stosu
K08     Dla każdego sąsiada y wierzchołka x wykonuj K09...K12 ; przeglądamy sąsiadów
K09:         Jeśli y = v, to zakończ z wynikiem true ; ścieżka znaleziona
K10:         Jeśli visited[y] = true, to następny obieg pętli K08 ; szukamy sąsiadów nieodwiedzonych
K11:         S.push(y) ; sąsiada umieszczamy na stosie
K12:         visited[y] ← true ; i oznaczamy jako odwiedzonego
K13: Zakończ z wynikiem false ; nie ma ścieżki
 
Algorytm przejścia DFSscc(v,n,graf,cn,C)
Wejście
v  –  wierzchołek startowy, v C
n  –  liczba wierzchołków w grafie, n C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
cn  –  numer bieżącej silnie spójnej składowej, cn C
C  –  n elementowa tablica numerów silnie spójnych składowych
Wyjście:
Przeglądnięcie wszystkich wierzchołków grafu, do których prowadzą ścieżki z wierzchołka v. Jeśli z któregoś z tych wierzchołków prowadzi ścieżka powrotna do wierzchołka v, to w tablicy  C dla wierzchołka v i wierzchołka bieżącego zostanie ustawiona wartość cn.
Elementy pomocnicze:
u,w  –  wierzchołki, u,w C
S  –  pusty stos wierzchołków
visited  –  n elementowa logiczna tablica odwiedzin
Lista kroków:
K01: Utwórz n elementową tablicę visited  
K02: Ustaw elementy tablicy visited na false  
K03: S.push(v) ; umieszczamy wierzchołek startowy na stosie
K04: visited[v] ← true ; oznaczamy go jako odwiedzony
K05: C[v] ← cn ; ustawiamy numer składowej w C[v]
K06: Dopóki S.empty() = false, wykonuj K07...K13 ; przejście DFS
K07:     uS.top() ; pobieramy ze stosu wierzchołek
K08:     S.pop() ; pobrany wierzchołek usuwamy ze stosu
K09:     Jeśli (uv) (DFSBack(u,v,n,graf) = true), to C[u] ← cn ; sprawdzamy istnienie ścieżki powrotnej
K10     Dla każdego sąsiada w wierzchołka u wykonuj K11...K13 ; przeglądamy sąsiadów
K11:         Jeśli visited[w] = true, to następny obieg pętli K10 ; szukamy sąsiadów nieodwiedzonych
K12:         S.push(w) ; sąsiada umieszczamy na stosie
K13:         visited[w] ← true ; i oznaczamy jako odwiedzonego
K14: Zakończ  
 
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:
C  –  n elementowa tablica liczb całkowitych. Dla każdego wierzchołka v grafu C[v] zawiera numer silnie spójnej składowej, do której ten wierzchołek należy.
cn  –  liczba silnie spójnych składowych, cn C
Elementy pomocnicze:
v  –  numer wierzchołka w grafie, v C
Lista kroków:
K01: Utwórz n elementową tablicę C  
K02: Wyzeruj tablicę C  
K03: cn ← 0 ; inicjujemy licznik składowych
K04: Dla v = 0,1,...,n-1 wykonuj K05...K07 ; przechodzimy przez kolejne wierzchołki grafu
K05:     Jeśli C[v] > 0, to następny obieg pętli K04 ; szukamy wierzchołka nowej składowej
K06:     cncn + 1 ; zwiększamy licznik
K07:     DFSscc(v,n,graf,cn,C) ; uruchamiamy przejście DFS od wierzchołka v
K08: Zakończ  

 

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 skierowanego, wyszukuje w nim wszystkie silnie spójne składowe, a następnie podaje należące do nich numery wierzchołków w grafie.

Przykładowe dane:

       13 27
0 1 0 4
1 2 1 4 1 5 1 8 1 11
2 6
3 1 3 7
4 8
5 2 5 8
6 5 6 7 6 9
8 4
9 5 9 7
10 8 10 11
11 8 11 9 11 12
12 3 12 6 12 9


Lazarus
// Wyznaczanie silnie spójnych składowych
// Data: 18.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program scc;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu
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 bada, czy istnieje ścieżka od u do v
// u    - wierzchołek startowy ścieżki
// v    - wierzchołek końcowy ścieżki
// n    - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// Wynik:
// true - istnieje ścieżka od u do v
// false- nie istnieje ścieżka od u do v
//----------------------------------------------
function DFSback(u,v,n : integer; var graf : TList) : boolean;
var
  i,x,y   : integer;
  S       : stack;
  visited : array of boolean;
  p       : PslistEl;
begin
  SetLength(visited,n);          // Tworzymy tablicę odwiedzin
  for i := 0 to n - 1 do         // i wypełniamy ją wartościami false
    visited[i] := false;

  S.init;                        // Tworzymy stos
  S.push(u);                     // Wierzchołek startowy na stos
  visited[u] := true;            // Oznaczamy go jako odwiedzonego

  while not S.empty do           // Uruchamiamy przejście DFS
  begin
    x := S.top;                  // Pobieramy wierzchołek ze stosu
    S.pop;                       // Pobrany wierzchołek usuwamy ze stosu

    p := graf[x];                // Przeglądamy sąsiadów
    while p <> nil do
    begin
      y := p^.v;                 // Numer sąsiada do y
      if y = v then              // Jeśli sąsiadem jest wierzchołek v,
      begin                      // to ścieżka znaleziona
        S.destroy;               // Zerujemy stos
        SetLength(visited,0);    // Usuwamy tablicę visited
        Exit(true);              // Kończymy z wynikiem true
      end;
      if not visited[y] then
      begin
        S.push(y);               // Nieodwiedzonego sąsiada umieszczamy na stosie
        visited[y] := true;      // i oznaczamy jako odwiedzonego
      end;
      p := p^.next;              // Następny sąsiad
    end;
  end;

  SetLength(visited,0);          // Usuwamy tablicę visited
  DFSback := false;              // i kończymy z wynikiem false
end;

// Procedura przechodzi przez graf od wierzchołka startowego v
// i umieszcza w tablicy C informację o przynależności wierzchołków
// do określonej silnie spójnej składowej.
// v    - wierzchołek startowy
// n    - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// cn   - numer silnie spójnej składowej
// C    - tablica numerów silnie spójnych składowych dla wierzchołków
// Wynik:
// Ustawia tablicę C
//--------------------------------------------------------------------
procedure DFSscc(v,n : integer; var graf : TList;
                 cn  : integer; var C : array of integer);
var
  i,u,w   : integer;
  S       : stack;
  visited : array of boolean;
  p       : PslistEl;
begin
  SetLength(visited,n);
  for i := 0 to n - 1 do visited[i] := false;

  S.init;

  S.push(v);                     // Wierzchołek startowy na stos
  visited[v] := true;            // Oznaczamy go jako odwiedzonego
  C[v] := cn;                    // Ustawiamy dla v numer składowej

  while not S.empty do           // Przejście DFS
  begin
    u := S.top;                  // Odczytujemy wierzchołek ze stosu
    S.pop;                       // Usuwamy ze stosu odczytany wierzchołek

    if (u <> v) and DFSback(u,v,n,graf) then C[u] := cn;

    p := graf[u];                // Przeglądamy sąsiadów wierzchołka u
    while p <> nil do
    begin
      w := p^.v;
      if not visited[w] then
      begin
        S.push(w);               // Nieodwiedzonego sąsiada umieszczamy na stosie
        visited[w] := true;      // i oznaczamy jako odwiedzonego
      end;
      p := p^.next;              // Następny sąsiad
    end;
  end;

  SetLength(visited,0);
end;

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

var
  n,m      : integer;            // Liczba wierzchołków i krawędzi
  graf     : TList;              // Tablica list sąsiedztwa grafu
  C        : array of integer;   // Tablica numerów składowych
  i,v,u,cn : integer;
  p,r      : PslistEl;

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

  SetLength(graf,n);             // Tworzymy tablice dynamiczne
  SetLength(C,n);

  // Inicjujemy tablice

  for i := 0 to n - 1 do
  begin
    graf[i] := nil;
    C[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 u
    p^.next := graf[v];      // i dodajemy na początek listy graf[v]
    graf[v] := p;
  end;

  // Wyznaczamy silnie spójne składowe

  cn := 0;                   // Inicjujemy licznik składowych

  for v := 0 to n - 1 do     // Przeglądamy kolejne wierzchołki grafu
    if C[v] = 0 then
    begin
      inc(cn);
      DFSscc(v,n,graf,cn,C); // Wyznaczamy silnie spójną składową
    end;

  // Wyświetlamy silnie spójne składowe

  writeln;

  for i := 1 to cn do
  begin
    write('SCC',i:3,' :');
    for v := 0 to n - 1 do
      if C[v] = i then write(v:3);
    writeln;
  end;

  writeln;

  // Usuwamy tablice dynamiczne

  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);
  SetLength(C,0);

end.
Code::Blocks
// Wyznaczanie silnie spójnych składowych
// Data: 18.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu

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 bada, czy istnieje ścieżka od u do v
// u    - wierzchołek startowy ścieżki
// v    - wierzchołek końcowy ścieżki
// n    - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// Wynik:
// true - istnieje ścieżka od u do v
// false- nie istnieje ścieżka od u do v
//----------------------------------------------
bool DFSback(int u, int v, int n, slistEl ** graf)
{
  int i,x,y;
  stack S;
  bool * visited;
  slistEl * p;

  visited = new bool [n];        // Tworzymy tablicę odwiedzin
  for(i = 0; i < n; i++)         // i wypełniamy ją wartościami false
    visited[i] = false;

  S.push(u);                     // Wierzchołek startowy na stos
  visited[u] = true;             // Oznaczamy go jako odwiedzonego

  while(!S.empty())              // Uruchamiamy przejście DFS
  {
    x = S.top();                 // Pobieramy wierzchołek ze stosu
    S.pop();                     // Pobrany wierzchołek usuwamy ze stosu

    for(p = graf[x]; p; p = p->next) // Przeglądamy sąsiadów
    {
      y = p->v;                  // Numer sąsiada do y
      if(y == v)                 // Jeśli sąsiadem jest wierzchołek v,
      {                          // to ścieżka znaleziona
        delete [] visited;       // Usuwamy tablicę visited
        return true;             // Kończymy z wynikiem true
      }
      if(!visited[y])
      {
        S.push(y);               // Nieodwiedzonego sąsiada umieszczamy na stosie
        visited[y] = true;       // i oznaczamy jako odwiedzonego
      }
    }
  }

  delete [] visited;             // Usuwamy tablicę visited
  return false;                  // i kończymy z wynikiem false
}

// Procedura przechodzi przez graf od wierzchołka startowego v
// i umieszcza w tablicy C informację o przynależności wierzchołków
// do określonej silnie spójnej składowej.
// v    - wierzchołek startowy
// n    - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// cn   - numer silnie spójnej składowej
// C    - tablica numerów silnie spójnych składowych dla wierzchołków
// Wynik:
// Ustawia tablicę C
//--------------------------------------------------------------------
void DFSscc(int v, int n, slistEl ** graf, int cn, int * C)
{
  int i,u,w;
  stack S;
  bool * visited;
  slistEl * p;

  visited = new bool [n];
  for(i = 0; i < n; i++) visited[i] = false;

  S.push(v);                     // Wierzchołek startowy na stos
  visited[v] = true;             // Oznaczamy go jako odwiedzonego
  C[v] = cn;                     // Ustawiamy dla v numer składowej

  while(!S.empty())              // Przejście DFS
  {
    u = S.top();                 // Odczytujemy wierzchołek ze stosu
    S.pop();                     // Usuwamy ze stosu odczytany wierzchołek

    if((u != v) && DFSback(u,v,n,graf)) C[u] = cn;

    for(p = graf[u]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka u
    {
      w = p->v;
      if(!visited[w])
      {
        S.push(w);               // Nieodwiedzonego sąsiada umieszczamy na stosie
        visited[w] = true;       // i oznaczamy jako odwiedzonego
      }
    }
  }

  delete [] visited;
}

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

int main()
{
  int n,m;                   // Liczba wierzchołków i krawędzi
  slistEl ** graf;           // Tablica list sąsiedztwa
  int * C;                   // Tablica z numerami spójnych składowych
  int i,v,u,cn;
  slistEl *p,*r;

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

  graf = new slistEl * [n];  // Tworzymy tablice dynamiczne
  C = new int [n];

  // Inicjujemy tablice

  for(i = 0; i < n; i++)
  {
    graf[i] = NULL;
    C[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;
  }

  // Wyznaczamy silnie spójne składowe

  cn = 0;                    // Inicjujemy licznik składowych

  for(v = 0; v <= n - 1; v++) // Przeglądamy kolejne wierzchołki grafu
    if(!C[v]) DFSscc(v,n,graf,++cn,C); // Wyznaczamy silnie spójną składową


  // Wyświetlamy silnie spójne składowe

  cout << endl;

  for(i = 1; i <= cn; i++)
  {
    cout << "SCC" << setw(3) << i << " :";
    for(v = 0; v < n; v++) if(C[v] == i) cout << setw(3) << v;
    cout << endl;
  }

  cout << endl;

  // Usuwamy tablice dynamiczne

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

  return 0;
}
Free Basic
' Wyznaczanie silnie spójnych składowych
' Data: 18.01.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu

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 bada, czy istnieje ścieżka od u do v
' u    - wierzchołek startowy ścieżki
' v    - wierzchołek końcowy ścieżki
' n    - liczba wierzchołków w grafie
' graf - tablica list sąsiedztwa
' Wynik:
' 1    - istnieje ścieżka od u do v
' 0    - nie istnieje ścieżka od u do v
'----------------------------------------------
Function DFSback(ByVal u As Integer, ByVal v As integer, ByVal n As integer, _
	              ByVal graf As slistEl Ptr Ptr) As Integer
  Dim As integer i,x,y
  Dim As stack S
  Dim As Byte Ptr visited
  Dim As slistEl Ptr  p

  visited = New Byte [n]         ' Tworzymy tablicę odwiedzin
  For i = 0 To n - 1             ' i wypełniamy ją wartościami false
    visited[i] = 0
  Next

  S.push(u)                      ' Wierzchołek startowy na stos
  visited[u] = 1                 ' Oznaczamy go jako odwiedzonego

  While S.empty() = 0            ' Uruchamiamy przejście DFS
    x = S.top()                  ' Pobieramy wierzchołek ze stosu
    S.pop()                      ' Pobrany wierzchołek usuwamy ze stosu

    p = graf[x]
    While p                      ' Przeglądamy sąsiadów
      y = p->v                   ' Numer sąsiada do y
      If y = v Then              ' Jeśli sąsiadem jest wierzchołek v, to ścieżka znaleziona 
        Delete [] visited        ' Usuwamy tablicę visited
        return 1                 ' Kończymy z wynikiem true
      End If
      
      If visited[y] = 0 Then 
        S.push(y)                ' Nieodwiedzonego sąsiada umieszczamy na stosie
        visited[y] = 1           ' i oznaczamy jako odwiedzonego
      End If
      p = p->Next                ' Następny sąsiad
    Wend
  Wend

  Delete [] visited              ' Usuwamy tablicę visited
  Return 0                       ' i kończymy z wynikiem false
End Function

' Procedura przechodzi przez graf od wierzchołka startowego v
' i umieszcza w tablicy C informację o przynależności wierzchołków
' do określonej silnie spójnej składowej.
' v    - wierzchołek startowy
' n    - liczba wierzchołków w grafie
' graf - tablica list sąsiedztwa
' cn   - numer silnie spójnej składowej
' C    - tablica numerów silnie spójnych składowych dla wierzchołków
' Wynik:
' Ustawia tablicę C
'--------------------------------------------------------------------
Sub DFSscc(ByVal v As integer, ByVal n As integer, _
	        ByVal graf As slistEl Ptr ptr, _
	        ByVal cn As integer, ByVal C As Integer Ptr)

  Dim As Integer i,u,w
  Dim As stack S
  Dim As Byte Ptr visited
  Dim As slistEl Ptr p

  visited = New Byte [n]
  For i = 0 To n - 1
  	 visited[i] = 0
  Next

  S.push(v)                      ' Wierzchołek startowy na stos
  visited[v] = 1                 ' Oznaczamy go jako odwiedzonego
  C[v] = cn                      ' Ustawiamy dla v numer składowej
  
  While S.empty() = 0            ' Przejście DFS
    u = S.top()                  ' Odczytujemy wierzchołek ze stosu
    S.pop()                      ' Usuwamy ze stosu odczytany wierzchołek

    If (u <> v) AndAlso (DFSback(u,v,n,graf) = 1) Then C[u] = cn                  

    p = graf[u]
    While p                      ' Przeglądamy sąsiadów wierzchołka u
      w = p->v
      If visited[w] = 0 Then 
        S.push(w)                ' Nieodwiedzonego sąsiada umieszczamy na stosie
        visited[w] = 1           ' i oznaczamy jako odwiedzonego
      End If
      p = p->Next
    Wend
  Wend

  Delete [] visited
End Sub

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

Dim As Integer n,m               ' Liczba wierzchołków i krawędzi
Dim As slistEl Ptr Ptr graf      ' Tablica list sąsiedztwa grafu
Dim As Integer Ptr C
Dim As Integer i,v,u,cn
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 tablice dynamiczne
C = New Integer [n]

' Inicjujemy tablice

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

' Odczytujemy kolejne definicje krawędzi.

For i = 1 To m
  Input #1,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 A[v]
  graf[v] = p
Next

Close #1

' Wyznaczamy silnie spójne składowe

cn = 0                    ' Inicjujemy licznik składowych

For v = 0 To n - 1        ' Przeglądamy kolejne wierzchołki grafu
  If C[v] = 0 Then
  	  cn += 1
  	  DFSscc(v,n,graf,cn,C) ' Wyznaczamy silnie spójną składową
  EndIf
Next

' Wyświetlamy silnie spójne składowe

Print

For i = 1 To cn
  Print Using "SCC### :"; i;
  For v = 0 To n - 1
    If C[v] = i Then Print Using "###";v;
  Next
  Print
Next

Print

' Usuwamy tablice dynamiczne

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

Delete [] graf
Delete [] C

End
Wynik
13 27
0 1 0 4
1 2 1 4 1 5 1 8 1 11
2 6
3 1 3 7
4 8
5 2 5 8
6 5 6 7 6 9
8 4
9 5 9 7
10 8 10 11
11 8 11 9 11 12
12 3 12 6 12 9

SCC  1 :  0
SCC  2 :  1  3 11 12
SCC  3 :  2  5  6  9
SCC  4 :  4  8
SCC  5 :  7
SCC  6 : 10

 

Algorytm Kosaraju

Algorytm Kosaraju wyznacza wszystkie silnie spójne składowe grafu w czasie liniowym. Wykorzystuje on stos, dwa przejścia DFS oraz transpozycję grafu. Zasada działania tego algorytmu jest następująca:

 

Ustawiamy wszystkie wierzchołki grafu jako nieodwiedzone. Następnie przeglądamy je po kolei od pierwszego do ostatniego. Jeśli napotkamy wierzchołek nieodwiedzony (na początku algorytmu będzie to pierwszy wierzchołek grafu), to od tego wierzchołka uruchamiamy rekurencyjne przejście w głąb DFS. Zadaniem tego przejścia jest odwiedzenie wszystkich dostępnych wierzchołków, do których wiodą ścieżki z wierzchołka startowego. Dodatkowo DFS po zakończeniu rekurencyjnego odwiedzania sąsiadów umieszcza odwiedzony wierzchołek na stosie.

Gdy algorytm się zakończy, stos będzie zawierał wierzchołki w kolejności "czasu" ich odwiedzenia przez DFS. Na szczycie stosu będzie wierzchołek startowy.

Teraz dokonujemy transpozycji grafu i znów oznaczamy wszystkie wierzchołki jako nieodwiedzone. Następnie dopóki stos zawiera wierzchołki, pobieramy ze stosu wierzchołek i jeśli jest on nieodwiedzony, to w grafie transponowanym uruchamiamy drugie przejście DFS od tego wierzchołka. Wszystkie odwiedzone przez DFS wierzchołki należą do tej samej silnie spójnej składowej. Wystarczy je wypisywać lub zapamiętywać w miarę odwiedzania przez to drugie przejście DFS.

 

Algorytm Korsaraju wyszukiwania silnie spójnych składowych w grafie skierowanym

Algorytm przejścia DFSstack(v,visited,S,graf)
Wejście
v  –  wierzchołek startowy, u C
visited  –  tablica logiczna odwiedzin
S  –  stos wierzchołków
graf  –  graf zadany w dowolny sposób, algorytm tego nie precyzuje
Wyjście:
Wpisuje na stos wierzchołki w odwrotnej kolejności odwiedzin (pierwszy na szczycie stosu jest wierzchołek odwiedzony jako pierwszy).
Elementy pomocnicze:
u  –  wierzchołek, u C
Lista kroków:
K01: visited[v] ← true ; wierzchołek v oznaczamy jako odwiedzony
K02: Dla każdego sąsiada u wierzchołka v wykonuj K03 ; przeglądamy sąsiadów
K03:     Jeśli visited[u] = false, to DFSstack(u,visited,S,graf) ; jeśli sąsiad nieodwiedzony, to uruchamiamy rekurencyjne DFS
K04: S.push(v) ; po przetworzeniu sąsiadów v umieszczamy na stosie
K05: Zakończ  

 

Algorytm przejścia DFSprint(v,visited,graf)
Wejście
v  –  wierzchołek startowy, v C
visited  –  tablica logiczna odwiedzin
graf  –  graf zadany w dowolny sposób, algorytm tego nie precyzuje
Wyjście:
Wypisuje na wyjście kolejno odwiedzane wierzchołki.
Elementy pomocnicze:
u  –  wierzchołek, u C
Lista kroków:
K01: visited[v] ← true ; wierzchołek v oznaczamy jako odwiedzony
K02: Pisz v ; wyprowadzamy wierzchołek na wyjście
K03: Dla każdego sąsiada u wierzchołka v wykonuj K03 ; przeglądamy sąsiadów
K04:     Jeśli visited[u] = false, to DFSprint(u,visited,graf) ; jeśli sąsiad nieodwiedzony, to uruchamiamy rekurencyjne DFS
K05: Zakończ  

 

Algorytm główny
Wejście
n  –  liczba wierzchołków w grafie, n C
graf  –  graf zadany w dowolny sposób, algorytm tego nie precyzuje
Wyjście:
Wypisuje na wyjście wierzchołki należące do silnie spójnych składowych.
Elementy pomocnicze:
visited  –  n elementowa logiczna tablica odwiedzin
S  –  stos wierzchołków
v  –  wierzchołek, v C
cn  –  licznik silnie spójnych składowych, cn C
Lista kroków:
K01: Utwórz n elementową tablicę visited  
K02: Tablicę visited wypełnij wartościami false  
K03: Utwórz pusty stos S  
K04: Dla v = 0,1,...,n-1 wykonuj K05 ; przeglądamy kolejne wierzchołki grafu
K05:     Jeśli visited[v] = false, to DSFstack(v,visited,S,graf) ; w wierzchołku nieodwiedzonym uruchamiamy DFS
K06: Transponuj graf  
K07: Tablicę visited wypełnij wartościami false  
K08: cn ← 0 ; zerujemy licznik silnie spójnych składowych
K09: Dopóki S.empty() = false, wykonuj K10...K14 ; teraz przetwarzamy wierzchołki zgodnie ze stosem
K10:     vS.top();   S.pop() ; pobieramy wierzchołek ze stosu
K11:     Jeśli visited[v] = true, to następny obieg pętli K09 ; szukamy wierzchołka nieodwiedzonego
K12:     cncn + 1 ; zwiększamy licznik silnie spójnych składowych
K13:     Pisz "SCC ",cn," : "  
K14:     DFSprint(v,visited,graf) ; wypisujemy wierzchołki silnie spójnej składowej
K15: Zakończ  

 

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 skierowanego, wyszukuje w nim wszystkie silnie spójne składowe, a następnie podaje należące do nich numery wierzchołków w grafie.

Przykładowe dane:

       13 27
0 1 0 4
1 2 1 4 1 5 1 8 1 11
2 6
3 1 3 7
4 8
5 2 5 8
6 5 6 7 6 9
8 4
9 5 9 7
10 8 10 11
11 8 11 9 11 12
12 3 12 6 12 9


Lazarus
// Wyznaczanie silnie spójnych składowych
// Algorytm Korsaraju
// Data: 26.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program scc;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu
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;

// Przechodzi graf algorytmem DFS, umieszczając na stosie
// napotkane po drodze wierzchołki.
// v       - numer wierzchołka startowego
// visited - tablica odwiedzin
// S       - stos
// graf    - tablica list sąsiedztwa
//--------------------------------------------------------
procedure DFSstack(v : integer; var visited : array of boolean;
                   var S : stack; var graf : TList);
var
  p : PslistEl;
begin
  visited[v] := true;            // Oznaczamy v jako odwiedzony

  p := graf[v];                  // Przeglądamy sąsiadów v
  while p <> nil do
  begin
    if not visited[p^.v] then DFSstack(p^.v,visited,S,graf);
    p := p^.next;
  end;

  S.push(v);
end;

// Wyświetla wierzchołki kolejno odwiedzane przez DFS
// v       - wierzchołek startowy
// visited - tablica odwiedzin
// graf    - tablica list sąsiedztwa
//---------------------------------------------------
procedure DFSprint(v : integer; var visited : array of boolean;
                   var graf : TList);
var
  p : PslistEl;
begin
  visited[v] := true;
  write(v:3);
  p := graf[v];
  while p <> nil do
  begin
    if not visited[p^.v] then DFSprint(p^.v,visited,graf);
    p := p^.next;
  end;
end;

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

var
  n,m      : integer;            // Liczba wierzchołków i krawędzi
  A,AT     : TList;              // Tablice list sąsiedztwa
  visited  : array of boolean;
  S        : stack;
  i,v,u,cn : integer;
  p,r      : PslistEl;

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

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

  // Inicjujemy tablice

  for i := 0 to n - 1 do
  begin
    A[i]  := nil;
    AT[i] := nil;
  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 u
    p^.next := A[v];         // i dodajemy na początek listy graf[v]
    A[v] := p;
  end;

  writeln;

  // Wyznaczamy silnie spójne składowe

  SetLength(visited,n);       // Tworzymy tablicę odwiedzin
  for i := 0 to n - 1 do      // i wypełniamy ją wartościami false
    visited[i] := false;

  S.init;                     // Tworzymy pusty stos

  for v := 0 to n - 1 do      // Przeglądamy kolejne wierzchołki grafu
    if not visited[v] then DFSstack(v,visited,S,A);

  // Transponujemy graf

  for v := 0 to n - 1 do      // Przeglądamy kolejne wierzchołki
  begin
    p := A[v];                // Przeglądamy sąsiadów v
    while p <> nil do
    begin
      new(r);                 // Tworzymy nowy element listy
      r^.v := v;              // Zapamiętujemy w nim wierzchołek v
      r^.next := AT[p^.v];    // i dodajemy do listy sąsiada
      AT[p^.v] := r;

      p := p^.next;           // Następny sąsiad
    end;
  end;

  for v := 0 to n - 1 do      // Zerujemy tablicę odwiedzin
    visited[v] := false;

  cn := 0;                    // Inicjujemy licznik składowych

  while not S.empty do        // Przetwarzamy wierzchołki ze stosu
  begin
    v := S.top; S.pop;        // Pobieramy wierzchołek ze stosu
    if not visited[v] then
    begin
      inc(cn);                // Zwiększamy licznik składowych
      write('SCC',cn:3,' :');
      DFSprint(v,visited,AT);
      writeln;
    end;
  end;

  // Usuwamy tablice 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;
    p := AT[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);
  SetLength(AT,0);
  SetLength(visited,0);

  S.destroy;
end.
Code::Blocks
// Wyznaczanie silnie spójnych składowych
// Algorytm Korsaraju
// Data: 26.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu

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

// Przechodzi graf algorytmem DFS, umieszczając na stosie
// napotkane po drodze wierzchołki.
// v       - numer wierzchołka startowego
// visited - tablica odwiedzin
// S       - stos
// graf    - tablica list sąsiedztwa
//--------------------------------------------------------
void DFSstack(int v, bool * visited, stack & S, slistEl ** graf)
{
  slistEl * p;

  visited[v] = true;             // Oznaczamy v jako odwiedzony

  // Przeglądamy sąsiadów v
  for(p = graf[v]; p; p = p->next)
    if(!visited[p->v]) DFSstack(p->v,visited,S,graf);

  S.push(v);
}

// Wyświetla wierzchołki kolejno odwiedzane przez DFS
// v       - wierzchołek startowy
// visited - tablica odwiedzin
// graf    - tablica list sąsiedztwa
//---------------------------------------------------
void DFSprint(int v, bool * visited, slistEl ** graf)
{
  slistEl * p;

  visited[v] = true;
  cout << setw(3) << v;
  for(p = graf[v]; p; p = p->next)
    if(!visited[p->v]) DFSprint(p->v,visited,graf);
}

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

int main()
{
  int n,m;                       // Liczba wierzchołków i krawędzi
  slistEl **A, **AT;             // Tablice list sąsiedztwa
  bool * visited;
  stack S;
  int i,v,u,cn;
  slistEl *p,*r;

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

  A  = new slistEl * [n];        // Tworzymy tablice dynamiczne
  AT = new slistEl * [n];

  // Inicjujemy tablice

  for(i = 0; i < n; i++) A[i] = AT[i] = NULL;

  // 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 u
    p->next = A[v];              // i dodajemy na początek listy graf[v]
    A[v] = p;
  }

  cout << endl;

  // Wyznaczamy silnie spójne składowe

  visited = new bool [n];        // Tworzymy tablicę odwiedzin
  for(i = 0; i < n; i++)         // i wypełniamy ją wartościami false
    visited[i] = false;

  for(v = 0; v < n; v++)         // Przeglądamy kolejne wierzchołki grafu
    if(!visited[v]) DFSstack(v,visited,S,A);

  // Transponujemy graf

  for(v = 0; v < n; v++)         // Przeglądamy kolejne wierzchołki
      // Przeglądamy sąsiadów v
    for(p = A[v]; p; p = p->next)
    {
      r = new slistEl;           // Tworzymy nowy element listy
      r->v = v;                  // Zapamiętujemy w nim wierzchołek v
      r->next = AT[p->v];        // i dodajemy do listy sąsiada
      AT[p->v] = r;
    }

  for(v = 0; v < n; v++)         // Zerujemy tablicę odwiedzin
    visited[v] = false;

  cn = 0;                        // Inicjujemy licznik składowych

  while(!S.empty())              // Przetwarzamy wierzchołki ze stosu
  {
    v = S.top(); S.pop();        // Pobieramy wierzchołek ze stosu
    if(!visited[v])
    {
      cout << "SCC" << setw(3) << ++cn << " :";
      DFSprint(v,visited,AT);
      cout << endl;
    }
  }

  // Usuwamy tablice dynamiczne

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

  return 0;
}
Free Basic
' Wyznaczanie silnie spójnych składowych
' Algorytm Korsaraju
' Data: 25.01.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu

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

' Przechodzi graf algorytmem DFS, umieszczając na stosie
' napotkane po drodze wierzchołki.
' v       - numer wierzchołka startowego
' visited - tablica odwiedzin
' S       - stos
' graf    - tablica list sąsiedztwa
'--------------------------------------------------------
Sub DFSstack(ByVal v As integer, _
	          ByVal visited As Byte Ptr, _ 
	          ByRef S As stack, _ 
	          ByVal graf As slistEl Ptr Ptr)

  Dim As slistEl Ptr p

  visited[v] = 1                 ' Oznaczamy v jako odwiedzony

  ' Przeglądamy sąsiadów v
  p = graf[v]
  While p
    If (visited[p->v] = 0) Then DFSstack(p->v,visited,S,graf)
     p = p->Next
  Wend
  
  S.push(v)
End Sub

' Wyświetla wierzchołki kolejno odwiedzane przez DFS
' v       - wierzchołek startowy
' visited - tablica odwiedzin
' graf    - tablica list sąsiedztwa
'---------------------------------------------------
Sub DFSprint(ByVal v As integer, _ 
	          ByVal visited As Byte ptr, _ 
	          ByVal graf As slistEl Ptr Ptr)

  Dim As slistEl Ptr p

  visited[v] = 1
  Print Using "###";v;
  p = graf[v]
  while p <> 0
    If (visited[p->v] = 0) Then DFSprint(p->v,visited,graf)
    p = p->Next
  Wend
End Sub

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

Dim As Integer n,m              ' Liczba wierzchołków i krawędzi
Dim As slistEl Ptr Ptr A,AT     ' Tablice list sąsiedztwa
Dim As Byte Ptr visited
Dim As stack S
Dim As Integer i,v,u, cn
Dim As slistEl Ptr p,r

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
AT = New slistEl Ptr [n]

' Inicjujemy tablice

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

' Odczytujemy kolejne definicje krawędzi.

For i = 1 To m
  Input #1,v,u                   ' Wierzchołki tworzące krawędź
  p = New slistEl                ' 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
Next

Close #1

Print

' Wyznaczamy silnie spójne składowe

visited = New Byte [n]           ' Tworzymy tablicę odwiedzin
For i = 0 To n - 1               ' i wypełniamy ją wartościami false
  visited[i] = 0
Next

For v = 0 To n - 1               ' Przeglądamy kolejne wierzchołki grafu
  If visited[v] = 0 Then DFSstack(v,visited,S,A)
Next

' Transponujemy graf

For v = 0 To n - 1               ' Przeglądamy kolejne wierzchołki
  ' Przeglądamy sąsiadów v
  p = A[v]
  While p
    r = New slistEl              ' Tworzymy nowy element listy
    r->v = v                     ' Zapamiętujemy w nim wierzchołek v
    r->next = AT[p->v]           ' i dodajemy do listy sąsiada
    AT[p->v] = r
    p = p->Next
  Wend
Next

For v = 0 To n - 1               ' Zerujemy tablicę odwiedzin
  visited[v] = 0
Next

cn = 0                           ' Inicjujemy licznik składowych

While  S.empty() = 0             ' Przetwarzamy wierzchołki ze stosu
  v = S.top(): S.pop()           ' Pobieramy wierzchołek ze stosu
  If visited[v] = 0 Then
    cn += 1
    Print Using "SCC### :";cn;
    DFSprint(v,visited,AT)
    Print
  End If
Wend

' Usuwamy tablice dynamiczne

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

Delete [] A
Delete [] AT
Delete [] visited

End
Wynik
13 27
0 1 0 4
1 2 1 4 1 5 1 8 1 11
2 6
3 1 3 7
4 8
5 2 5 8
6 5 6 7 6 9
8 4
9 5 9 7
10 8 10 11
11 8 11 9 11 12
12 3 12 6 12 9

SCC  1 : 10
SCC  2 :  0
SCC  3 :  1  3 12 11
SCC  4 :  9  6  2  5
SCC  5 :  7
SCC  6 :  4  8

 

Algorytm Tarjana

Opisany wcześniej algorytm Koraju wymagał wykonania dwóch przejść DFS (jednego w grafie wyjściowym oraz jednego w grafie transponowanym). Poniżej przedstawiamy algorytm opracowany przez Tarjana, który wykonuje tylko jedno przejście DFS, jest zatem szybszy.

 

Zasada działania algorytmu Tarjana opiera się na przejściu rekurencyjnym DFS, w trakcie którego numerujemy kolejno odwiedzane wierzchołki. Przy odwiedzaniu wierzchołków DFS wyznacza minimalny numer wierzchołka, do którego istnieje ścieżka biegnąca od bieżącego wierzchołka. Numer ten jest zapamiętywany w parametrze Low związanym z każdym wierzchołkiem grafu. Parametr Low można prosto wyznaczyć na podstawie numerów oraz parametrów Low wierzchołków sąsiednich.

 

Algorytm Tarjana wykorzystuje stos do składowania odwiedzanych wierzchołków oraz do identyfikowania silnie spójnych składowych. Efektem działania tego algorytmu jest lista, która zawiera listy wierzchołków należących do tej samej silnie spójnej składowej grafu wyjściowego.

 

Algorytm Tarjana wyszukiwania silnie spójnych składowych w grafie skierowanym

Algorytm przejścia DFSscc(v,cvn,VN,VLow,VS,S,Lscc,graf)
Wszystkie parametry za wyjątkiem v mogą być zrealizowane jako globalne, co zmniejszy zapotrzebowanie na pamięć przy wywoływaniach rekurencyjnych.
Wejście
v  –  wierzchołek startowy, v C
cvn  –  numer bieżącego wierzchołka, cvn C
VN  –  tablica numerów wierzchołków, które ustala DFSscc()
VLow  –  tablica parametrów Low
VS  –  tablica logiczna, która informuje, czy dany wierzchołek jest na stosie S
S  –  stos wierzchołków
Lscc  –  jednokierunkowa lista silnie spójnych składowych. Każda silnie spójna składowa jest jednokierunkową listą wierzchołków, które do niej należą.
graf  –  graf zadany w dowolny sposób, algorytm tego nie precyzuje
Wyjście:
Lista silnie spójnych składowych Lscc.
Elementy pomocnicze:
u  –  wierzchołek, u C
sccp,p  –  wskaźniki do elementu listy wierzchołków
listp  –  wskaźnik do elementu listy list
Lista kroków:
K01: cvncvn + 1 ; zwiększamy numer wierzchołka
K02: VN[v] ← cvn ; i zapamiętujemy go w tablicy VN
K03: VLow[v] ← cvn ; oraz wstępnie w tablicy VLow
K04: S.push(v) ; wierzchołek umieszczamy na stosie
K05: VS[v] ← true ; i zapamiętujemy w VS, że jest on na stosie
K06: Dla każdego sąsiada u wierzchołka v wykonuj K07...K12 ; przeglądamy kolejnych sąsiadów wierzchołka v
K07:     Jeśli VN[u] = 0, to idź do K11 ; sprawdzamy, czy wierzchołek był odwiedzony
K08:     Jeśli VS[u] = false, to następny obieg pętli K06 ; sprawdzamy, czy wierzchołek u jest na stosie
K09:     VLow[v] ← min(VLow[v], VN[u]) ; jeśli tak, to wyznaczamy najmniejszy numer dostępnego wierzchołka z v
K10:     Następny obieg pętli K06 ; i kontynuujemy pętlę
K11:     DFSscc(u,cvn,VN,VLow,VS,S,Lscc,graf) ; wierzchołek nieodwiedzony: rekurencyjnie wywołujemy dla niego DFSscc()
K12:     VLow[v] ← min(VLow[v], VLow[u]) ; i wyznaczamy najmniejszy numer dostępnego wierzchołka z v
K13: Jeśli VLow[v] ≠ VN[v], to zakończ ; sprawdzamy, czy znaleźliśmy całą silnie spójną składową
K14: sccp ← nil ; tworzymy pustą listę wierzchołków
K15:     uS.top() ; pobieramy ze stosu wierzchołek silnie spójnej składowej
K16:     S,pop() ; pobrany wierzchołek usuwamy ze stosu
K17:     VS[u] ← false ; zaznaczamy, że wierzchołka już nie ma na stosie
K18:     Utwórz nowy element listy wierzchołków ; wierzchołek dodajemy do listy silnie spójnej składowej
K19     p ← adres nowego elementu listy wierzchołków  
K20:     (pv) ← u  
K21:     (pnext) ← sccp  
K22:     sccpp  
K23: Jeśli uv, to idź do K15 ; pętlę kontynuujemy, aż do dotarcia do korzenia składowej
K24: Utwórz nowy element listy list ; listę wierzchołków sccp dodajemy do listy Lscc
K25: listp ← adres nowego elementu listy list  
K26: (listpv) ← sccp  
K27 (listpnext) ← Lscc  
K28: Lscclistp  
K29: Zakończ  

 

Algorytm główny
Wejście
n  –  liczba wierzchołków w grafie, n C
graf  –  graf zadany w dowolny sposób, algorytm tego nie precyzuje
Wyjście:
Wypisuje na wyjście wierzchołki należące do silnie spójnych składowych.
Elementy pomocnicze:
v  –  numer wierzchołka, v C
cvn  –  numer bieżącego wierzchołka, cvn C
VN  –  tablica numerów wierzchołków, które ustala DFSscc()
VLow  –  tablica parametrów Low
VS  –  tablica logiczna, która informuje, czy dany wierzchołek jest na stosie S
S  –  stos wierzchołków
Lscc  –  jednokierunkowa lista silnie spójnych składowych. Każda silnie spójna składowa jest jednokierunkową listą wierzchołków, które do niej należą.
listp  –  wskaźnik elementu listy składowych
p  –  wskaźnik listy wierzchołków
Lista kroków:
K01: Utwórz pusty stos S  
K02: Utwórz n elementową tablicę VN i wyzeruj ją  
K03: Utwórz n elementową tablicę VS i wyzeruj ją  
K04: Utwórz n elementową tablicę VLow  
K05: cvn ← 0 ; zerujemy numer wierzchołka
K06: Lscc ← nil ; tworzymy pustą listę silnie spójnych składowych
K07: Dla v = 0,1,...,n - 1 wykonuj K08 ; przeglądamy kolejne wierzchołki grafu
K08:     Jeśli VN[v] = 0, to DFSscc(v,cvn,VN,VLow,VS,S,Lscc,graf) ; w wierzchołkach nieodwiedzonych uruchamiamy DFS
K09: listpLscc ; przeglądamy listę silnie spójnych składowych
K10: Dopóki listp ≠ nil, wykonuj K11...K16  
K11:     p ← (listpv) ; przeglądamy listę wierzchołków
K12:     Dopóki p ≠ nil, wykonuj K13...K14  
K13:         Pisz (pv) ; wypisujemy wierzchołki silnie spójnej składowej
K14:         p ← (pnext) ; następny wierzchołek
K15:     Przejdź do następnego wiersza wydruku  
K16:     listp ← (listpnext) ; następna lista
K17: Zakończ  

 

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 skierowanego, wyszukuje w nim wszystkie silnie spójne składowe za pomocą algorytmu Tarjana, a następnie podaje należące do nich numery wierzchołków w grafie.

Przykładowe dane:

       13 27
0 1 0 4
1 2 1 4 1 5 1 8 1 11
2 6
3 1 3 7
4 8
5 2 5 8
6 5 6 7 6 9
8 4
9 5 9 7
10 8 10 11
11 8 11 9 11 12
12 3 12 6 12 9


Lazarus
// Wyznaczanie silnie spójnych składowych
// Algorytm Tarjana
// Data: 2.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program scc;

// Typy danych
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

// Typ danych dla listy silnie spójnych składowych
  PsslistEl = ^sslistEl;
  sslistEl = record
    next : PsslistEl;
    v    : PslistEl;
  end;

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

// Zmienne globalne
//-----------------
var
  n,m,cvn  : integer;
  VN,VLow  : array of integer;
  VS       : array of boolean;
  S        : stack;
  graf     : array of PslistEl;
  Lscc     : PsslistEl;

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

// Zwraca mniejszą z dwóch liczb
//------------------------------
function min(a,b : integer) : integer;
begin
  if a < b then min := a else min := b;
end;

// Procedura wykonująca przejście DFS i wyznaczająca
// silnie spójną składową.
// v - wierzchołek startowy dla DFS
//---------------------------------------------------
procedure DFSscc(v : integer);
var
  u : integer;
  sccp,p : PslistEl;
  listp  : PsslistEl;
begin
  inc(cvn);                     // Zwięlszamy numer wierzchołka
  VN[v]   := cvn;               // Numerujemy bieżący wierzchołek
  VLow[v] := cvn;               // Ustalamy wstępnie parametr Low
  S.push(v);                    // Wierzchołek na stos
  VS[v]   := true;              // Zapamiętujemy, że v jest na stosie

  p := graf[v];                 // Przeglądamy listę sąsiadów
  while p <> nil do
  begin
    if VN[p^.v] = 0 then        // Jeśli sąsiad jest nieodwiedzony, to
    begin
      DFSscc(p^.v);             // wywołujemy dla niego rekurencyjnie DFS
      VLow[v] := min(VLow[v],VLow[p^.v]); // i obliczamy parametr Low dla v
    end
    else if VS[p^.v] then       // Jeśli sąsiad odwiedzony, lecz wciąż na stosie,
      VLow[v] := min(VLow[v],VN[p^.v]); // to wyznaczamy parametr Low dla v
    p := p^.next;
  end;

  if VLow[v] = VN[v] then       // Sprawdzamy, czy mamy kompletną składową
  begin
    sccp := nil;                // Dodajemy tę składową do listy składowych
    repeat
      u := S.top;               // Pobieramy wierzchołek ze stosu
      S.pop;                    // Pobrany wierzchołek usuwamy ze stosu
      VS[u] := false;           // Zapamiętujemy, że nie ma go już na stosie
      new(p);                   // Nowy element listy wierzchołków
      p^.v := u;                // Zapisujemy w nim wierzchołek
      p^.next := sccp;          // dodajemy go na początek listy
      sccp := p;
    until u = v;                // Kontynuujemy aż do korzenia składowej

    new(listp);                 // Nowy element listy składowych
    listp^.v := sccp;           // Zapisujemy w nim listę
    listp^.next := Lscc;        // i dołączamy na początek listy składowych
    Lscc := listp;
  end;
end;

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

var
  i,v,u      : integer;
  p,r        : PslistEl;
  listp,listr: PsslistEl;

begin
  S.init;                           // Tworzymy pusty stos

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

  SetLength(graf,n);                // Tworzymy tablice dynamiczne
  SetLength(VN,n);
  SetLength(VLow,n);
  SetLength(VS,n);

  // Inicjujemy tablice

  for i := 0 to n - 1 do
  begin
    graf[i] := nil;
    VN[i]   := 0;
    VS[i]   := false;
  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 u
    p^.next := graf[v];      // i dodajemy na początek listy graf[v]
    graf[v] := p;
  end;

  writeln;

  // Wyznaczamy silnie spójne składowe

  cvn := 0;                  // Zerujemy numer wierzchołka

  Lscc := nil;               // Tworzymy pustą listę składowych

  for v := 0 to n - 1 do     // Przeglądamy kolejne wierzchołki
    if VN[v] = 0 then DFSscc(v); // W wierzchołku nieodwiedzonym uruchamiamy DFS

  listp := Lscc;             // Przeglądamy listę składowych
  cvn := 0;                  // cvn jest teraz licznikiem składowych
  while listp <> nil do
  begin
    inc(cvn);                // Zwiększamy numer składowej
    write('SCC',cvn:3,' :'); // Wyświetlamy numer składowej
    p := listp^.v;           // Przeglądamy listę wierzchołków
    while p <> nil do
    begin
      write(p^.v:3);         // Wyświetlamy wierzchołek składowej
      p := p^.next;          // Następny wierzchołek na liście
    end;
    writeln;
    listp := listp^.next;    // Następna składowa na liście
  end;

  // Usuwamy zmienne dynamiczne

  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;

  listp := Lscc;
  while listp <> nil do
  begin
    p := listp^.v;
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
    listr := listp;
    listp := listp^.next;
    dispose(listr);
  end;

  SetLength(graf,0);
  SetLength(VN,0);
  SetLength(VLow,0);
  SetLength(VS,0);

  S.destroy;
end.
Code::Blocks
// Wyznaczanie silnie spójnych składowych
// Algorytm Tarjana
// Data: 2.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych

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

// Typ danych dla listy silnie spójnych składowych

struct sslistEl
{
  sslistEl * next;
  slistEl  * 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);
};

// Zmienne globalne
//-----------------

int      n,m,cvn,*VN,*VLow;
bool     *VS;
stack    S;
slistEl  **graf;
sslistEl *Lscc;

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

// Procedura wykonująca przejście DFS i wyznaczająca
// silnie spójną składową.
// v - wierzchołek startowy dla DFS
//---------------------------------------------------
void DFSscc(int v)
{
  int u;
  slistEl  *sccp,*p;
  sslistEl *listp;

  VN[v] = VLow[v] = ++cvn;      // Numerujemy wierzchołek i ustawiamy wstępnie parametr Low
  S.push(v);                    // Wierzchołek na stos
  VS[v] = true;                 // Zapamiętujemy, że v jest na stosie

  for(p = graf[v];p;p = p->next) // Przeglądamy listę sąsiadów
    if(!VN[p->v])               // Jeśli sąsiad jest nieodwiedzony, to
    {
      DFSscc(p->v);             // wywołujemy dla niego rekurencyjnie DFS
      VLow[v] = min(VLow[v],VLow[p->v]); // i obliczamy parametr Low dla v
    }
    else if(VS[p->v])           // Jeśli sąsiad odwiedzony, lecz wciąż na stosie,
      VLow[v] = min(VLow[v],VN[p->v]); // to wyznaczamy parametr Low dla v

  if(VLow[v] == VN[v])          // Sprawdzamy, czy mamy kompletną składową
  {
    sccp = NULL;                // Dodajemy tę składową do listy składowych
    do
    {
      u = S.top();              // Pobieramy wierzchołek ze stosu
      S.pop();                  // Pobrany wierzchołek usuwamy ze stosu
      VS[u] = false;            // Zapamiętujemy, że nie ma go już na stosie
      p = new slistEl;          // Nowy element listy wierzchołków
      p->v = u;                 // Zapisujemy w nim wierzchołek
      p->next = sccp;           // dodajemy go na początek listy
      sccp = p;
    } while(u != v);            // Kontynuujemy aż do korzenia składowej

    listp = new sslistEl;       // Nowy element listy składowych
    listp->v = sccp;            // Zapisujemy w nim listę
    listp->next = Lscc;         // i dołączamy na początek listy składowych
    Lscc = listp;
  }
}

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

int main()
{
  int i,v,u;
  slistEl *p,*r;
  sslistEl *listp,*listr;

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

  graf = new slistEl * [n];     // Tworzymy tablice dynamiczne
  VN   = new int [n];
  VLow = new int [n];
  VS   = new bool [n];

  // Inicjujemy tablice

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

  // 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 u
    p->next = graf[v];          // i dodajemy na początek listy graf[v]
    graf[v] = p;
  }

  cout << endl;

  // Wyznaczamy silnie spójne składowe

  cvn = 0;                      // Zerujemy numer wierzchołka

  Lscc = NULL;                  // Tworzymy pustą listę składowych

  for(v = 0; v < n; v++)        // Przeglądamy kolejne wierzchołki
    if(!VN[v]) DFSscc(v);       // W wierzchołku nieodwiedzonym uruchamiamy DFS

  cvn = 0;                      // cvn jest teraz licznikiem składowych
  for(listp = Lscc;listp;listp = listp->next) // Przeglądamy listę składowych
  {
    cout << "SCC" << setw(3) << ++cvn << " :"; // Wyświetlamy numer składowej
    for(p = listp->v;p;p = p->next) // Przeglądamy listę wierzchołków
      cout << setw(3) << p->v;  // Wyświetlamy wierzchołek składowej
    cout << endl;
  }

  // Usuwamy zmienne dynamiczne

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

  listp = Lscc;
  while(listp)
  {
    p = listp->v;
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
    listr = listp;
    listp = listp->next;
    delete listr;
  }

  delete [] graf;
  delete [] VN;
  delete [] VLow;
  delete [] VS;

  return 0;
}
Free Basic
' Wyznaczanie silnie spójnych składowych
' Algorytm Tarjana
' Data: 2.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy danych

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type sslistEl
  next As sslistEl Ptr
  v As slistEl Ptr
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

' Zmienne globalne
'-----------------

Dim Shared As Integer n,m,cvn
Dim Shared As Integer Ptr VN,VLow
Dim Shared As Byte Ptr VS
Dim Shared As stack S
Dim Shared As slistEl Ptr Ptr graf
Dim Shared As sslistEl Ptr Lscc

'---------------------
' 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 zwraca mniejszą z liczb a i b
'--------------------------------------
Function min(ByVal a As Integer, ByVal b As Integer) As Integer
	If a < b Then
		Return a
	Else
		Return b
	EndIf
End Function

' Procedura wykonująca przejście DFS i wyznaczająca
' silnie spójną składową.
' v - wierzchołek startowy dla DFS
'---------------------------------------------------
Sub DFSscc(ByVal v As Integer)
  Dim As Integer u
  Dim As slistEl Ptr sccp,p
  Dim As sslistEl Ptr listp

  cvn += 1                      ' Zwiększamy bieżący numer wierzchołka
  VN[v] = cvn                   ' Numerujemy wierzchołek
  VLow[v] = cvn                 ' i ustawiamy wstępnie parametr Low
  S.push(v)                     ' Wierzchołek na stos
  VS[v] = 1                     ' Zapamiętujemy, że v jest na stosie

  p = graf[v]
  While p                       ' Przeglądamy listę sąsiadów
    If VN[p->v] = 0 Then        ' Jeśli sąsiad jest nieodwiedzony, to
      DFSscc(p->v)              ' wywołujemy dla niego rekurencyjnie DFS
      VLow[v] = min(VLow[v],VLow[p->v]) ' i obliczamy parametr Low dla v
    ElseIf VS[p->v] = 1 Then    ' Jeśli sąsiad odwiedzony, lecz wciąż na stosie,
      VLow[v] = min(VLow[v],VN[p->v]) ' to wyznaczamy parametr Low dla v
    End If
    p = p->Next
  Wend
  
  If VLow[v] = VN[v] Then       ' Sprawdzamy, czy mamy kompletną składową
    sccp = 0                    ' Dodajemy tę składową do listy składowych
    Do
      u = S.top()               ' Pobieramy wierzchołek ze stosu
      S.pop()                   ' Pobrany wierzchołek usuwamy ze stosu
      VS[u] = 0                 ' Zapamiętujemy, że nie ma go już na stosie
      p = new slistEl           ' Nowy element listy wierzchołków
      p->v = u                  ' Zapisujemy w nim wierzchołek
      p->next = sccp            ' dodajemy go na początek listy
      sccp = p
    Loop While u <> v           ' Kontynuujemy aż do korzenia składowej

    listp = new sslistEl        ' Nowy element listy składowych
    listp->v = sccp             ' Zapisujemy w nim listę
    listp->next = Lscc          ' i dołączamy na początek listy składowych
    Lscc = listp
  End If
End Sub

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

Dim As Integer i,v,u
Dim As slistEl Ptr p,r
Dim As sslistEl Ptr listp,listr

Open Cons For Input As #1

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

graf = New slistEl Ptr [n]       ' Tworzymy tablice dynamiczne
VN   = New Integer [n]
VLow = New Integer [n]
VS   = New Byte [n]

' Inicjujemy tablice

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

' Odczytujemy kolejne definicje krawędzi.

For i = 1 To m
  Input #1,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 A[v]
  graf[v] = p
Next

Close #1

Print

' Wyznaczamy silnie spójne składowe

cvn = 0                         ' Zerujemy numer wierzchołka

Lscc = 0                        ' Tworzymy pustą listę składowych

For v = 0 To n - 1              ' Przeglądamy kolejne wierzchołki
  If VN[v] = 0 Then DFSscc(v)   ' W wierzchołku nieodwiedzonym uruchamiamy DFS
Next

cvn = 0                         ' cvn jest teraz licznikiem składowych
listp = Lscc
While listp                     ' Przeglądamy listę składowych
  cvn += 1
  Print Using "SCC### :";cvn;   ' Wyświetlamy numer składowej
  p = listp->v
  While p                       ' Przeglądamy listę wierzchołków
    Print Using "###";p->v;     ' Wyświetlamy wierzchołek składowej
    p = p->Next                 ' Następny wierzchołek
  Wend  
  Print
  listp = listp->Next           ' Następna składowa
Wend

' Usuwamy tablice dynamiczne

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

listp = Lscc
While listp
  p = listp->v
  While p
    r = p
    p = p->Next
    Delete r
  Wend
  listr = listp
  listp = listp->Next
  Delete listr
Wend

Delete [] graf
Delete [] VN
Delete [] VLow
Delete [] VS

End
Wynik
13 27
0 1 0 4
1 2 1 4 1 5 1 8 1 11
2 6
3 1 3 7
4 8
5 2 5 8
6 5 6 7 6 9
8 4
9 5 9 7
10 8 10 11
11 8 11 9 11 12
12 3 12 6 12 9

SCC  1 : 10
SCC  2 :  0
SCC  3 :  1 11 12  3
SCC  4 :  9  5  2  6
SCC  5 :  7
SCC  6 :  4  8

 

 


   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