Kosaraju's algoritme: Gids voor sterk verbonden componenten

Kosaraju's algoritme vindt de sterk samenhangende componenten (SCC's) van een gerichte graaf. Een SCC is een groep knopen waarin elke knoop elke andere knoop kan bereiken. Het algoritme voert twee diepte-eerstzoekopdrachten uit: de eerste legt de volgorde vast waarin knopen klaar zijn, en de tweede draait op de graaf met alle randen omgekeerd, waarbij knopen in omgekeerde voltooiingsvolgorde worden verwerkt. Elke boom van de tweede zoekopdracht is één SCC. Het algoritme loopt in O(V + E) tijd.

Als je elke SCC samenperst tot één knoop, blijft er een gerichte graaf zonder cycli over. Daarom duiken SCC's op bij afhankelijkheidsanalyse, deadlockdetectie, 2-SAT en elk probleem waarbij cycli eerst moeten worden samengeperst.

De twee passes, stap voor stap

1. Voer DFS uit over de hele graaf. Wanneer een knoop klaar is (alle uitgaande buren zijn verwerkt), zet je hem op een lijst.
2. Keer elke rand om om de getransponeerde graaf te krijgen.
3. Loop door de voltooiingslijst van achter naar voor. Voor elke nog niet bezochte knoop voer je DFS uit op de getransponeerde graaf. Alles wat die zoekopdracht bereikt, is één SCC.

Beide lussen moeten bij elke onbezochte knoop beginnen, niet alleen bij knoop 0, omdat de graaf niet samenhangend hoeft te zijn.

Een uitgewerkt voorbeeld

Neem 8 knopen en deze randen:

0 → 1, 1 → 2, 2 → 0      (cycle A: 0, 1, 2)
2 → 3
3 → 4, 4 → 5, 5 → 3      (cycle B: 3, 4, 5)
6 → 5
6 → 7, 7 → 6             (cycle C: 6, 7)

De SCC's zouden 2, 5 en 7 moeten zijn.

Eerste pass

Begin DFS bij 0 en ga 0 → 1 → 2 → 3 → 4 → 5. Knoop 5 heeft nergens nieuws naartoe te gaan, dus die is als eerste klaar, dan 4, dan 3. Terug bij 2 is er niets meer over, dus 2, 1 en 0 zijn klaar. Knoop 6 is nog niet bezocht, dus begin daar: 5 is al klaar, dus ga naar 7, die klaar is, en dan 6. De voltooiingsvolgorde is:

5, 4, 3, 2, 1, 0, 7, 6

Tweede pass

Keer elke rand om en verwerk knopen vanaf het einde van die lijst: 6 eerst. In de omgekeerde graaf kan 6 alleen 7 bereiken, dus 7 is de eerste SCC. De volgende onbezochte is 0, die in de omgekeerde graaf 2 en 1 bereikt, wat 2 oplevert. De rand 2 → 3 wijst nu 3 → 2, maar 2 is al toegewezen, dus de zoekopdracht stopt daar. Ten slotte bereikt 3 de knopen 5 en 4, wat 5 oplevert.

Waarom het werkt

Denk aan de graaf van SCC's (elke component samengeperst tot één knoop), die geen cycli heeft. In de eerste pass hoort de knoop die als laatste klaar is altijd bij een "bron"-component, een component zonder inkomende randen van andere niet-toegewezen componenten. Het omkeren van de randen maakt van die bron een put, dus een DFS die daar begint kan zijn eigen component niet verlaten. Zodra die component is verwijderd, geldt hetzelfde argument voor de volgende.

In een sollicitatiegesprek is dat meestal het niveau van bewijs dat wordt verwacht: de voltooiingsvolgorde kiest een veilige startcomponent, en het omkeren van de randen voorkomt dat de tweede zoekopdracht naar andere componenten lekt.

Python-implementatie

Deze versie gebruikt iteratieve DFS, zodat hij niet tegen Python's recursielimiet aanloopt bij diepe grafen.

from collections import defaultdict

def kosaraju(n, edges):
    graph = defaultdict(list)
    reverse = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        reverse[v].append(u)

    # Pass 1: record vertices in the order they finish (iterative DFS)
    visited = [False] * n
    order = []
    for start in range(n):
        if visited[start]:
            continue
        visited[start] = True
        stack = [(start, iter(graph[start]))]
        while stack:
            node, neighbors = stack[-1]
            for nxt in neighbors:
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append((nxt, iter(graph[nxt])))
                    break
            else:
                stack.pop()
                order.append(node)

    # Pass 2: DFS on the reversed graph, latest finish time first
    visited = [False] * n
    components = []
    for start in reversed(order):
        if visited[start]:
            continue
        visited[start] = True
        component = []
        stack = [start]
        while stack:
            node = stack.pop()
            component.append(node)
            for nxt in reverse[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append(nxt)
        components.append(component)
    return components


edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 5), (6, 7), (7, 6)]
print(kosaraju(8, edges))  # [[6, 7], [0, 2, 1], [3, 5, 4]]

De volgorde van knopen binnen elke component hangt af van de traversal, dus vergelijk componenten als sets in je tests. We hebben deze implementatie gecontroleerd tegen een brute-force bereikbaarheidscheck op 2.000 willekeurige grafen.

Complexiteit

De ruimte is O(V + E) voor de twee adjacency lists, plus O(V) voor de visited-array, de voltooiingsvolgorde en de stack.

Fouten die het algoritme breken

De meest voorkomende bug is knopen vastleggen wanneer DFS ze voor het eerst bereikt in plaats van wanneer ze klaar zijn. Andere zijn vergeten de voltooiingsvolgorde om te keren voor de tweede pass, de tweede pass op de originele graaf uitvoeren in plaats van op de omgekeerde, de visited-array niet wissen tussen de passes, en alleen vanaf knoop 0 beginnen waardoor niet-samenhangende delen worden overgeslagen. Recursieve DFS kan ook de stack laten overlopen bij lange ketens, daarom is de code hierboven iteratief.

Goede testgevallen: één enkele knoop, een knoop met een self-loop, één grote cyclus, een eenrichtingsketen (elke knoop is zijn eigen SCC), twee cycli verbonden door één rand, en een niet-samenhangende graaf.

Kosaraju vs. Tarjan

Beide lopen in O(V + E). Kosaraju doet twee passes en bouwt de omgekeerde graaf, wat het makkelijker maakt om uit te leggen en correct te krijgen. Tarjan's algoritme doet het in één pass zonder omgekeerde graaf, maar houdt discovery-indexen en low-link-waarden bij op een stack, wat meer state is om uit elkaar te houden. In een sollicitatiegesprek gebruik je degene die je correct kunt implementeren en uitleggen. Als de interviewer om een enkele pass vraagt, is dat een hint voor Tarjan.

Graafproblemen oefenen

Traceer het voorbeeld hierboven één keer met de hand voordat je code schrijft; de meeste bugs komen naar voren als een verkeerde voltooiingsvolgorde. Gerelateerde gidsen: Floyd–Warshall voor alle-paren kortste paden, Bellman–Ford voor grafen met negatieve randen, en onze Big O cheat sheet. Als je YesToTheOffer gebruikt bij het oefenen van code, kan de screenshot coding help je aanpak controleren, en het sessietranscript laat zien of je je redenering duidelijk hebt uitgelegd.