Starkt sammanhängande komponenter med Kosaraju
Kör DFS på den ursprungliga grafen för att få en avslutningsordning, transponera grafen och kör DFS igen i omvänd avslutningsordning för att identifiera SCC:er.
Starkt sammanhängande komponenter med Kosaraju är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 4 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Definition av starkt sammanhängande komponenter
En starkt sammanhängande komponent (SCC) i en riktad graf är en maximal mängd noder där det finns en väg från varje nod till alla andra noder i mängden. Om noderna A, B och C till exempel bildar en cykel (A→B→C→A) ingår de alla i samma SCC. En ensam nod utan en självloop utgör sin egen SCC. SCC:er synliggör den cykliska strukturen i en riktad graf.
Kosarajus algoritm: två DFS-genomgångar
Kosarajus algoritm hittar alla SCC:er i O(V + E) med två DFS-genomgångar. Genomgång 1: kör DFS på den ursprungliga grafen och lägg noderna på en stack i slutförandeordning (efterordning). Genomgång 2: kör DFS på den transponerade (omvända) grafen och behandla noderna i omvänd slutförandeordning (ta bort dem från stacken). Varje DFS-träd i genomgång 2 är en SCC.
Varför Kosaraju fungerar
I genomgång 1 är den SCC vars DFS-träd avslutas sist den som inte har några utgående kanter till andra SCC:er (en ”sink”-SCC i kondenserings-DAG:en). I den transponerade grafen har denna SCC inga inkommande kanter från andra SCC:er — därför förblir DFS därifrån inom denna SCC i genomgång 2. Varje efterföljande DFS i genomgång 2 stannar inom sin egen SCC eftersom alla kanter mellan SCC:er har vänts och leder tillbaka till SCC:er som redan har besökts.
Genomgång 1: skapa slutförandeordningen
Kör DFS på den ursprungliga grafen och lägg varje nod på en stack när den är färdig (efterordning). Vi bryr oss inte om komponenterna i den här genomgången — bara om slutförandeordningen. Den nod som avslutas sist finns i en ”source”-SCC i kondenserings-DAG:en.
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_graphGenomgång 2: DFS på den transponerade grafen
Ta bort noder från slutförandestacken (störst slutförandetid först) och kör DFS på den transponerade grafen. Varje DFS från en obesökt nod hittar exakt en SCC. Markera alla noder som nås i denna DFS som tillhörande samma komponent.
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 similarTransponering av grafen
Den transponerade grafen vänder på varje kant: om originalgrafen har u → v har den transponerade grafen v → u. Transponering bevarar SCC:er — om A och B ligger i samma SCC i originalgrafen ligger de kvar i samma SCC i den transponerade grafen (eftersom alla vägar vänds men fortfarande förbinder noderna). Genom att bygga den transponerade grafen när indata läses in (som visas ovan) undviker du ett separat transponeringssteg.
Iterativ version för stora grafer
För stora grafer ersätter du rekursiv DFS med iterativ DFS med en explicit stack för att undvika Pythons rekursionsgräns. Den iterativa versionen lägger noder på stacken, bearbetar dem och upprätthåller en separat returmarkering för att simulera 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')Tarjans algoritm: alternativ för SCC
Tarjans algoritm hittar SCC:er i en enda DFS-genomgång, jämfört med Kosarajus två genomgångar. Den upprätthåller en stack med noder och tilldelar varje nod en upptäcktstid och ett low-link-värde. När en nods upptäcktstid är lika med dess low-link-värde är den roten i en SCC. Tarjans algoritm är något mer komplex att implementera, men du slipper bygga den transponerade grafen. Båda har komplexiteten O(V + E).
Tillämpningar av SCC:er
SCC:er används inom: (1) kompilatoroptimering — identifiering av ömsesidigt rekursiva funktioner. (2) analys av sociala nätverk — hitta tätt sammanhållna gemenskaper. (3) 2-SAT-problemet — avgöra om klausuler med två literaler är uppfyllbara. (4) webbgenomsökning — identifiera kluster av sidor med många korslänkar. (5) kondensations-DAG — efter att SCC:erna har hittats är grafens kondensation en DAG, vilket möjliggör topologisk analys av cykliska grafer.
Kondensations-DAG
Kondensationen av en riktad graf kontraherar varje SCC till en enda nod och lägger till en kant mellan två supernoder om det finns en kant mellan deras ingående SCC:er. Resultatet är alltid en DAG — du kan köra topologisk sortering på den. Detta gör det möjligt att tillämpa algoritmer som bara fungerar på DAG:ar, till exempel DP, på allmänna riktade grafer genom att arbeta med deras kondensation.
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)]Antalet SCC:er och grafegenskaper
Antalet SCC:er i en riktad graf visar dess cykliska struktur. En DAG har n SCC:er, eftersom varje nod utgör sin egen SCC. En starkt sammanhängande graf har exakt 1 SCC. I allmänhet bildar SCC:erna en DAG när de kondenseras — kondensationen. Om kondensations-DAG:en har en unik källa, det vill säga en nod med ingrad 0, och en unik sänka, det vill säga en nod med utgrad 0, gäller vissa sammanhängningsegenskaper. Dessa egenskaper testas i problem om nåbarhet efter att minimalt antal kanter har lagts till.
Snabbkontroll
Testa din förståelse av koncepten från den här lektionen i Data Structures & Algorithms — Coding Interview Prep.
Lektionssammanfattning
I den här lektionen lärde du dig: SCC:er är maximala mängder där varje nod kan nås från alla andra, Kosarajus algoritm använder två DFS-genomgångar — först på ursprungsgrafen för avslutningsordningen och sedan på den transponerade grafen, samt att kondensationen av en godtycklig riktad graf är en DAG som kan användas för vidare analys. Härnäst bygger vi datastrukturer med TrieNode för insert, search och prefixoperationer.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Starkt sammanhängande komponenter med Kosaraju” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Starkt sammanhängande komponenter med Kosaraju”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Starkt sammanhängande komponenter med Kosaraju”?
Kör DFS på den ursprungliga grafen för att få en avslutningsordning, transponera grafen och kör DFS igen i omvänd avslutningsordning för att identifiera SCC:er. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Starkt sammanhängande komponenter med Kosaraju”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Kahns algoritm: topologisk sortering med BFS
- Topologisk sortering med DFS i postorder
- Course Schedule I och II
- Starkt sammanhängande komponenter med Kosaraju