Sterk samenhangende componenten met Kosaraju
Voer DFS uit op de oorspronkelijke graaf om de finish-volgorde te bepalen, transposeer de graaf en voer opnieuw DFS uit in omgekeerde finish-volgorde om SCC's te identificeren.
Sterk samenhangende componenten met Kosaraju is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Sterk samenhangende componenten gedefinieerd
Een sterk samenhangende component (SCC) van een gerichte graaf is een maximale verzameling knopen waarvoor er binnen de verzameling een pad bestaat van elke knoop naar elke andere knoop. Als de knopen A, B en C bijvoorbeeld een cyclus vormen (A→B→C→A), zitten ze allemaal in dezelfde SCC. Eén knoop zonder lus naar zichzelf vormt zijn eigen SCC. SCC's onthullen de cyclische structuur van een gerichte graaf.
Algoritme van Kosaraju: twee DFS-rondes
Het algoritme van Kosaraju vindt alle SCC's in O(V + E) met twee DFS-rondes. Ronde 1: voer DFS uit op de oorspronkelijke graaf en plaats knopen in volgorde van voltooiing op een stapel (postorder). Ronde 2: voer DFS uit op de getransponeerde (omgekeerde) graaf en verwerk de knopen in omgekeerde volgorde van voltooiing (haal ze van de stapel). Elke DFS-boom in ronde 2 vormt één SCC.
Waarom Kosaraju werkt
In ronde 1 is de SCC waarvan de DFS-boom als laatste wordt voltooid de SCC zonder uitgaande kanten naar andere SCC's, een doel-SCC in de condensatie-DAG. In de getransponeerde graaf heeft deze SCC geen inkomende kanten vanuit andere SCC's. DFS die vanuit deze SCC start, blijft daarom binnen die SCC. Elke volgende DFS in ronde 2 blijft binnen zijn eigen SCC, omdat alle kanten tussen SCC's zijn omgedraaid en terugwijzen naar SCC's die al zijn bezocht.
Ronde 1: voltooiingsvolgorde opbouwen
Voer DFS uit op de oorspronkelijke graaf en plaats elke knoop na voltooiing op een stapel (postorder). In deze ronde zijn de componenten niet belangrijk; het gaat alleen om de voltooiingsvolgorde. De knoop die als laatste wordt voltooid, bevindt zich in een bron-SCC van de condensatie-DAG.
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_graphRonde 2: DFS op de getransponeerde graaf
Haal knopen uit de stapel met de voltooiingsvolgorde, te beginnen met de grootste voltooiingstijd, en voer DFS uit op de getransponeerde graaf. Elke DFS vanuit een nog niet bezochte knoop ontdekt precies één SCC. Markeer alle knopen die tijdens deze DFS worden bereikt als onderdeel van dezelfde component.
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 similarDe graaf transponeren
De getransponeerde graaf keert elke kant om: als de oorspronkelijke graaf u → v bevat, bevat de getransponeerde graaf v → u. Transponeren behoudt de SCC's. Als A en B in de oorspronkelijke graaf in dezelfde SCC zitten, blijven ze ook in de getransponeerde graaf in dezelfde SCC, omdat alle paden worden omgekeerd maar nog steeds verbinding maken. Door de getransponeerde graaf tijdens het inlezen van de invoer op te bouwen, zoals hierboven wordt getoond, vermijd je een aparte transponeerstap.
Iteratieve versie voor grote grafen
Voor grote grafen vervang je recursieve DFS door iteratieve DFS met een expliciete stack om de recursielimiet van Python te omzeilen. De iteratieve versie plaatst knopen op de stack, verwerkt ze en houdt een afzonderlijke markering voor ‘terugkeren’ bij om postorder te simuleren.
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')Algoritme van Tarjan: alternatief voor SCC
Het algoritme van Tarjan vindt SCC's in één DFS-doorgang, vergeleken met de twee doorgangen van Kosaraju. Het houdt een stack met knopen bij en kent elke knoop een ontdekkingstijd en een low-linkwaarde toe. Wanneer de ontdekkingstijd van een knoop gelijk is aan zijn low-linkwaarde, is die knoop de wortel van een SCC. Het algoritme van Tarjan is iets complexer om te implementeren, maar voorkomt dat je de getransponeerde graaf moet opbouwen. Beide algoritmen zijn O(V + E).
Toepassingen van SCC's
SCC's worden gebruikt voor: (1) compileroptimalisatie — het identificeren van wederzijds recursieve functies. (2) sociale-netwerkanalyse — het vinden van hecht verbonden gemeenschappen. (3) het 2-SAT-probleem — bepalen of clausules met twee literalen vervulbaar zijn. (4) webcrawlen — het identificeren van clusters pagina's met veel kruislinks. (5) condensatie-DAG — nadat SCC's zijn gevonden, is de condensatie van de graaf een DAG, waardoor topologische analyse van cyclische grafen mogelijk wordt.
Condensatie-DAG
De condensatie van een gerichte graaf voegt elke SCC samen tot één enkele knoop en voegt een kant toe tussen twee superknopen als er een kant bestaat tussen hun onderliggende SCC's. Het resultaat is altijd een DAG — je kunt er een topologische sortering op uitvoeren. Hierdoor kunnen algoritmen die alleen op DAG's werken, zoals DP, op algemene gerichte grafen worden toegepast door met hun condensatie te werken.
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)]Aantal SCC's en graafeigenschappen
Het aantal SCC's in een gerichte graaf onthult de cyclische structuur ervan. Een DAG heeft n SCC's (elke knoop is zijn eigen SCC). Een sterk verbonden graaf heeft precies 1 SCC. In het algemeen vormen de SCC's een DAG wanneer ze worden samengevoegd — de condensatie. Als de condensatie-DAG een unieke bron (knoop met inkomende graad 0) en een unieke put (knoop met uitgaande graad 0) heeft, gelden bepaalde connectiviteitseigenschappen. Deze eigenschappen worden getoetst in problemen over bereikbaarheid na het toevoegen van een minimaal aantal kanten.
Korte controle
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep van deze les.
Samenvatting van de les
In deze les heb je geleerd: SCC's zijn maximale verzamelingen waarin elke knoop vanuit elke andere knoop bereikbaar is, Kosaraju gebruikt twee DFS-doorgangen — eerst op de oorspronkelijke graaf voor de voltooiingsvolgorde, daarna op de getransponeerde graaf, en de condensatie van elke gerichte graaf is een DAG die voor verdere analyse kan worden gebruikt. Hierna bouwen we TrieNode-gegevensstructuren voor invoegen, zoeken en prefixbewerkingen.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Sterk samenhangende componenten met Kosaraju” gratis?
Ja — de volledige tekst van “Sterk samenhangende componenten met Kosaraju” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Sterk samenhangende componenten met Kosaraju”?
Voer DFS uit op de oorspronkelijke graaf om de finish-volgorde te bepalen, transposeer de graaf en voer opnieuw DFS uit in omgekeerde finish-volgorde om SCC's te identificeren. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Sterk samenhangende componenten met Kosaraju”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Algoritme van Kahn: topologisch sorteren met BFS
- Topologisch sorteren met DFS in post-order
- Course Schedule I en II
- Sterk samenhangende componenten met Kosaraju