Silnie spójne składowe

Mirosław Mortka

Spójna składowa w grafie nieskierowanym to taki maksymalny zbiór wierzchołków, w którym pomiędzy każdą parą wierzchołków istnieją ścieżki.

Silnie spójna składowa w grafie skierowanym to taki maksymalny zbiór wierzchołków, w którym pomiędzy każdą parą wierzchołków istnieją ścieżki.

Dla grafu nieskierowanego wystarczy użyć dowolnego algorytmu przeszukiwania (DFS lub BFS). Wystarczy wówczas rozpocząć przeszukiwanie grafu od dowolnego wierzchołka. Wszystkie odwiedzone wówczas wierzchołki muszą należeć do jednej spójnej składowej. Każde wywołanie algorytmu przeszukiwania grafu wyznaczy nam jedną spójna składową.

Dla grafu skierowanego wykorzystamy algorytm DFS uruchomiony dwukrotnie. Najpierw za pomocą DFS wyznaczamy czasy przetworzenia wierzchołków w kolejności post-order. Następnie dla grafu transponowanego (to znaczy dla grafu z odwróconymi krawędziami) wywołujemy ponownie algorytm DFS w kolejności wyznaczonych malejących czasów przetworzenia wierzchołków. Te wierzchołki, które się znajdą w jednym drzewie powstałym w wyniku wywołania DFS należą do jednej silnie spójnej składowej.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License