Składowa Silnie Spójnie

Cel

W grafie skierowanym składowa silnie spójna to taka składowa w której pomiędzy dwoma dowolnymi wierzchołkami istnieje ścieżka. Jeden graf może zawierać wiele składowych silnie spójnych. Do wykrywanie takich składowych używa się algorytmu DFS.

Algorytm

W celu wykrycia Silnie Spójnych Składowych należy kolejno:

1. Przypisz indeksy wierzchołkom używając metody przeglądania post-order
2. Transponuj graf (tj. zamień kierunek krawędzi w grafie)
3. Stosujemy algorytm DFS dla wierzchołków w kolejności malejących indeksów, jedno przejście algorytmu wykrywa jedną składową
4. Odczytujemy Składowe Silnie Spójne

Przykład

Dany jest następujący graf skierowany:

Przykładowy Graf Skierowany

Pierwszy krok polega na poindeksowaniu elementów. W praktyce wystarczy po rekurencyjnym odwiedzieniu wszystkich sąsiadów dla danego wierzchołka jedynie odłożyć wierzchołek na stos. W ten sposóby otrzymujemy na stosie kolejno C, E, D, B, A jeśli algorytm DFS rozpoczniemy w wierzchołku A.

Teraz należy transponować graf czyli zamienić kierunek krawędzi.

Transponowany Graf

Resetujemy status odwiedzenia wierzchołków (tj. wszystkie są nieodwiedzone). Rozpoczynamy przeglądanie grafu według kolejności na stosie. Rozpoczynamy zatem od wierzchołka C. Wszystkie odwiedzone wierzchołki w danej "turze" algorytmu DFS to jedna składowa.

W tym grafie znajdują się trzy składowe (z czego dwie to pojedyncze wierzchołki, ale też liczy się je jako składowe):

Wykryte Składowe Silnie Spójne

Implementacja

Odwiedzanie wierzchołków

Metoda do odwiedzania wierzchołków będzie wykonywać rekurencyjne odwiedzanie kolejnych sąsiadów, którzy dotychczas pozostali nieodwiedzeni. Do tego należy przekazać macierz grafu, aktualną tablicę z informacji o tym, które wierzchołki są odwiedzone, aktualny indeks odwiedzanego wierzchołka oraz aktualny stos.

1. void OdwiedzWezel(int** macierz, int n, bool* tab, int u, stack<int> &stos) {
2.   tab[u] = true;
3.   for (int i = 0; i < n; i++) {
4.     if (macierz[u][i] > 0 && !tab[i]) {
5.       OdwiedzWezel(macierz, n, tab, i, stos);
6.     }
7.   }
8.   stos.push(u);
9. }

Jedyną różnicą pomiędzy typowym algorytmem DFS, a powyższym jest dodanie zapisywanie informacji na stosie. Przyda się wpierw do nadanie indeksów wierzchołkom, a następnie do szybkiego odczytania znalezionej składowej.

Transpozycja

W przypadku macierzy transpozycja grafu polega na zamianie wszystkich par (x, y) z (y, x) tak jak w algorytmie poniżej:

1. void TransponujGraf(int** macierz, int n) {
2.   for (int x = 0; x < n; x++) {
3.     for (int y = x; y < n; y++) {
4.       swap(macierz[x][y], macierz[y][x]);
5.     }
6.   }
7. }

Wyszukiwanie

Zgodnie z algorytmem pierwsza część polega na nadaniu indeksów wierzchołkom. Następnie resetujemy status odwiedzonych pól i transponujemy graf. Teraz potrzebny jest algorytm DFS, który przy każdym przejściu wyznaczy wierzchołki tworzące składową silnie spójną.

1. void SilnieSpojneSkladowe(int** macierz, int n) {
2.   bool* tab = new bool[n];
3.   for (int i = 0; i < n; i++) { tab[i] = false; }
4.   stack<int> stos;
5.   OdwiedzWezel(macierz, n, tab, 0, stos);
7.   TransponujGraf(macierz, n);
8.   for (int i = 0; i < n; i++) { tab[i] = false; }
9.   stack<int> sciezka;
10.   while (!stos.empty()) {
11.     int teraz = stos.top();
12.     stos.pop();
13.     if (!tab[teraz]) {
14.       OdwiedzWezel(macierz, n, tab, teraz, sciezka);
15.       while (!sciezka.empty()) {
16.         cout << sciezka.top() << " ";
17.         sciezka.pop();
18.       }
19.       cout << endl;
20.     }
21.   }
22. }

W celu zapisania wierzchołków w składowej do funkcji przekazujemy stos na który są dorzucane kolejne odwiedzane wierzchołki. Po zakończeniu są one zdejmowane ze stosu i wypisywane. Należy pamiętać, żeby nie szukać algorytmem DFS dla wierzchołków, które zostały odwiedzone w poprzednich składowych!

Testowanie funkcji

Do przetestowanie kodu można wykorzystać poniższy algorytm:

1. int main() {
2.   int n;
3.   cout << "Ile wierzcholkow ma graf?\n n = ";
4.   cin >> n;
5.   cout << "Podaj macierz:" << endl;
6.   int** macierz = new int*[n];
7.   for (int i = 0; i < n; i++) {
8.     macierz[i] = new int[n];
9.     for (int j = 0; j < n; j++)
10.       cin >> macierz[i][j];
11.   }
12.   SilnieSpojneSkladowe(macierz, n);
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Implementacja