Silnie spójne składowe za pomocą algorytmu Kosaraju
Uruchamiać DFS na grafie oryginalnym, aby uzyskać kolejność zakończenia, odwracać graf, a następnie ponownie uruchamiać DFS w odwrotnej kolejności zakończenia w celu identyfikacji SCC
Silnie spójne składowe za pomocą algorytmu Kosaraju to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Definicja silnie spójnych składowych
Silnie spójna składowa (SCC) grafu skierowanego to maksymalny zbiór wierzchołków, taki że z każdego wierzchołka można przejść ścieżką do każdego innego wierzchołka w tym zbiorze. Na przykład jeśli wierzchołki A, B i C tworzą cykl (A→B→C→A), wszystkie należą do tej samej SCC. Pojedynczy wierzchołek bez pętli własnej jest własną SCC. SCC ujawniają cykliczną strukturę grafu skierowanego.
Algorytm Kosaraju: dwa przebiegi DFS
Algorytm Kosaraju znajduje wszystkie SCC w czasie O(V + E), wykorzystując dwa przebiegi DFS. Przebieg 1: uruchom DFS na oryginalnym grafie i odkładaj wierzchołki na stos w kolejności kończenia przetwarzania (postorder). Przebieg 2: uruchom DFS na grafie transponowanym (odwróconym), przetwarzając wierzchołki w odwrotnej kolejności kończenia (zdejmując je ze stosu). Każde drzewo DFS w drugim przebiegu stanowi jedną SCC.
Dlaczego algorytm Kosaraju działa
W pierwszym przebiegu SCC, której drzewo DFS kończy się najpóźniej, nie ma krawędzi wychodzących do innych SCC (jest „źródłową” SCC w DAG-u kondensacji). W grafie transponowanym ta SCC nie ma krawędzi przychodzących z innych SCC, więc DFS rozpoczęty w jej wierzchołku pozostaje w jej obrębie podczas drugiego przebiegu. Każdy kolejny DFS w drugim przebiegu pozostaje w obrębie własnej SCC, ponieważ wszystkie krawędzie między SCC zostały odwrócone i prowadzą z powrotem do SCC już odwiedzonych.
Przebieg 1: tworzenie kolejności kończenia
Uruchom DFS na oryginalnym grafie i odkładaj każdy wierzchołek na stos po zakończeniu jego przetwarzania (postorder). W tym przebiegu nie interesują nas poszczególne składowe — liczy się tylko kolejność kończenia. Wierzchołek, którego przetwarzanie zakończy się jako ostatnie, będzie należeć do „źródłowej” SCC w DAG-u kondensacji.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graphPrzebieg 2: DFS na grafie transponowanym
Zdejmuj wierzchołki ze stosu kolejności kończenia (zaczynając od wierzchołka z największym czasem zakończenia) i uruchamiaj DFS na grafie transponowanym. Każdy DFS rozpoczęty w nieodwiedzonym wierzchołku odkrywa dokładnie jedną SCC. Oznacz wszystkie wierzchołki osiągnięte w tym DFS jako należące do tej samej składowej.
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarTransponowanie grafu
Graf transponowany odwraca każdą krawędź: jeśli w oryginalnym grafie istnieje u → v, w grafie transponowanym istnieje v → u. Transponowanie zachowuje SCC — jeśli A i B należą do tej samej SCC w grafie oryginalnym, pozostają w tej samej SCC w grafie transponowanym (ponieważ wszystkie ścieżki zostają odwrócone, ale nadal łączą te wierzchołki). Zbudowanie grafu transponowanego podczas wczytywania danych (jak pokazano powyżej) pozwala uniknąć osobnego kroku transponowania.
Iteracyjna wersja dla dużych grafów
W przypadku dużych grafów rekurencyjne DFS należy zastąpić iteracyjnym DFS z użyciem jawnego stosu, aby uniknąć limitu rekurencji w Pythonie. Wersja iteracyjna umieszcza wierzchołki na stosie, przetwarza je i korzysta z osobnego znacznika „return”, aby zasymulować porządek postorder.
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')Algorytm Tarjana: alternatywna metoda znajdowania SCC
Algorytm Tarjana znajduje SCC w jednym przebiegu DFS (w przeciwieństwie do dwóch przebiegów algorytmu Kosaraju). Utrzymuje stos wierzchołków oraz przypisuje każdemu wierzchołkowi czas odkrycia i wartość low-link. Gdy czas odkrycia wierzchołka jest równy jego wartości low-link, wierzchołek ten jest korzeniem SCC. Algorytm Tarjana jest nieco bardziej złożony w implementacji, ale pozwala uniknąć budowania grafu transponowanego. Złożoność obu algorytmów wynosi O(V + E).
Zastosowania SCC
SCC znajdują zastosowanie w: (1) optymalizacji kompilatorów — identyfikowaniu wzajemnie rekurencyjnych funkcji; (2) analizie sieci społecznościowych — wyszukiwaniu silnie powiązanych społeczności; (3) problemie 2-SAT — określaniu spełnialności klauzul z dwoma literałami; (4) crawlowaniu stron internetowych — identyfikowaniu klastrów stron z gęstą siecią wzajemnych odnośników; (5) grafie DAG kondensacji — po znalezieniu SCC kondensacja grafu jest grafem DAG, co umożliwia analizę topologiczną grafów cyklicznych.
Graf DAG kondensacji
Kondensacja grafu skierowanego zastępuje każdą SCC pojedynczym wierzchołkiem i dodaje krawędź między dwiema zagregowanymi w ten sposób częściami, jeśli między należącymi do nich SCC istnieje krawędź. Wynik zawsze jest grafem DAG — można na nim wykonać sortowanie topologiczne. Dzięki temu algorytmy działające tylko na grafach DAG, takie jak programowanie dynamiczne, można stosować do ogólnych grafów skierowanych, operując na ich kondensacji.
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]Liczba SCC a właściwości grafu
Liczba SCC w grafie skierowanym ujawnia jego strukturę cykliczną. Graf DAG ma n SCC (każdy wierzchołek tworzy własną SCC). Graf silnie spójny ma dokładnie 1 SCC. Ogólnie rzecz biorąc, po kondensacji SCC tworzą graf DAG — kondensację. Jeśli graf DAG kondensacji ma jedno źródło (wierzchołek o stopniu wejściowym 0) i jeden ujście (wierzchołek o stopniu wyjściowym 0), w kondensacji zachodzą określone właściwości spójności. Właściwości te są sprawdzane w zadaniach dotyczących osiągalności po dodaniu minimalnej liczby krawędzi.
Szybki test
Sprawdź swoją wiedzę na temat zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji dowiedział się Pan / dowiedziała się Pani, że: SCC to maksymalne zbiory, w których każdy wierzchołek jest osiągalny z każdego innego, algorytm Kosaraju korzysta z dwóch przebiegów DFS — najpierw na oryginalnym grafie w celu ustalenia kolejności zakończenia, a następnie na grafie transponowanym, a także że kondensacja dowolnego grafu skierowanego jest grafem DAG, który można wykorzystać do dalszej analizy. W następnej części zbudujemy struktury danych TrieNode na potrzeby operacji wstawiania, wyszukiwania i operacji na prefiksach.
Często zadawane pytania
Czy lekcja „Silnie spójne składowe za pomocą algorytmu Kosaraju” jest bezpłatna?
Tak — pełny tekst „Silnie spójne składowe za pomocą algorytmu Kosaraju” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Silnie spójne składowe za pomocą algorytmu Kosaraju”?
Uruchamiać DFS na grafie oryginalnym, aby uzyskać kolejność zakończenia, odwracać graf, a następnie ponownie uruchamiać DFS w odwrotnej kolejności zakończenia w celu identyfikacji SCC Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Silnie spójne składowe za pomocą algorytmu Kosaraju”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Algorytm Kahna: sortowanie topologiczne za pomocą BFS
- Sortowanie topologiczne DFS w kolejności postorder
- Course Schedule I i II
- Silnie spójne składowe za pomocą algorytmu Kosaraju