Algoritmo di Kosaraju: Guida ai Componenti Fortemente Connessi

L'algoritmo di Kosaraju trova le componenti fortemente connesse (SCC) di un grafo orientato. Una SCC è un gruppo di vertici in cui ogni vertice può raggiungere tutti gli altri. L'algoritmo esegue due ricerche in profondità: la prima registra l'ordine in cui i vertici terminano, la seconda viene eseguita sul grafo con tutti gli archi invertiti, prendendo i vertici in ordine inverso di terminazione. Ogni albero della seconda ricerca è una SCC. L'algoritmo gira in tempo O(V + E).

Se comprimi ogni SCC in un singolo nodo, quello che rimane è un grafo orientato senza cicli. Ecco perché le SCC compaiono nell'analisi delle dipendenze, nel rilevamento dei deadlock, nel 2-SAT e in qualsiasi problema in cui i cicli devono essere prima collassati.

Le due passate, passo per passo

1. Esegui una DFS su tutto il grafo. Quando un vertice termina (tutti i suoi vicini in uscita sono stati processati), inseriscilo in una lista.
2. Inverti ogni arco per ottenere il grafo trasposto.
3. Scorri la lista di terminazione dall'ultimo al primo. Per ogni vertice non ancora visitato, esegui una DFS sul grafo trasposto. Tutto ciò che quella ricerca raggiunge è una SCC.

Entrambi i cicli devono partire da ogni vertice non visitato, non solo dal vertice 0, perché il grafo potrebbe non essere connesso.

Un esempio svolto

Prendi 8 vertici e questi archi:

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)

Le SCC dovrebbero essere 2, 5 e 7.

Prima passata

Parti con la DFS da 0 e vai 0 → 1 → 2 → 3 → 4 → 5. Il vertice 5 non ha nessun nuovo posto dove andare, quindi termina per primo, poi 4, poi 3. Tornando a 2 non è rimasto nulla, quindi terminano 2, 1 e 0. Il vertice 6 non è stato visitato, quindi parti da lì: 5 è già terminato, quindi vai a 7, che termina, poi 6. L'ordine di terminazione è:

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

Seconda passata

Inverti ogni arco e processa i vertici dalla fine di quella lista: prima 6. Nel grafo invertito, 6 può raggiungere solo 7, quindi 7 è la prima SCC. Il prossimo non visitato è 0, che nel grafo invertito raggiunge 2 e 1, dando 2. L'arco 2 → 3 ora punta 3 → 2, ma 2 è già assegnato, quindi la ricerca si ferma lì. Infine, 3 raggiunge 5 e 4, dando 5.

Perché funziona

Pensa al grafo delle SCC (ogni componente compressa in un nodo), che non ha cicli. Nella prima passata, il vertice che termina per ultimo appartiene sempre a una componente "sorgente", una senza archi entranti da altre componenti non assegnate. Invertire gli archi trasforma quella sorgente in un pozzo, quindi una DFS avviata lì non può uscire dalla propria componente. Una volta rimossa quella componente, lo stesso ragionamento si applica alla successiva.

In un colloquio, di solito è questo il livello di dimostrazione atteso: l'ordine di terminazione sceglie una componente di partenza sicura, e invertire gli archi impedisce alla seconda ricerca di sconfinare in altre componenti.

Implementazione in Python

Questa versione usa una DFS iterativa, quindi non raggiungerà il limite di ricorsione di Python su grafi profondi.

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]]

L'ordine dei vertici all'interno di ogni componente dipende dalla traversata, quindi nei tuoi test confronta le componenti come insiemi. Abbiamo verificato questa implementazione contro un controllo di raggiungibilità a forza bruta su 2.000 grafi casuali.

Complessità

Lo spazio è O(V + E) per le due liste di adiacenza, più O(V) per l'array dei visitati, l'ordine di terminazione e lo stack.

Errori che lo mandano in tilt

Il bug più comune è registrare i vertici quando la DFS li raggiunge per la prima volta invece di quando terminano. Altri sono dimenticare di invertire l'ordine di terminazione per la seconda passata, eseguire la seconda passata sul grafo originale invece che su quello invertito, non azzerare l'array dei visitati tra le due passate e partire solo dal vertice 0 facendo saltare le parti disconnesse. La DFS ricorsiva può anche mandare in overflow lo stack su catene lunghe, ed è per questo che il codice sopra è iterativo.

Buoni casi di test: un singolo vertice, un vertice con un autoanello, un grande ciclo, una catena a senso unico (ogni vertice è una SCC a sé), due cicli uniti da un solo arco e un grafo disconnesso.

Kosaraju vs. Tarjan

Entrambi girano in O(V + E). Kosaraju fa due passate e costruisce il grafo invertito, il che lo rende più facile da spiegare e da implementare correttamente. L'algoritmo di Tarjan lo fa in una sola passata senza grafo invertito, ma tiene traccia degli indici di scoperta e dei valori low-link su uno stack, il che significa più stato da gestire. In un colloquio, usa quello che riesci a implementare correttamente e a spiegare. Se l'intervistatore chiede una singola passata, è un segnale per Tarjan.

Esercitarsi con i problemi sui grafi

Traccia l'esempio qui sopra a mano una volta prima di scrivere codice; la maggior parte dei bug si manifesta come un ordine di terminazione sbagliato. Guide correlate: Floyd–Warshall per i cammini minimi tra tutte le coppie, Bellman–Ford per i grafi con archi negativi e il nostro cheat sheet sulla Big O. Se usi YesToTheOffer nella pratica di coding, il suo aiuto al coding tramite screenshot può verificare il tuo approccio, e la trascrizione della sessione mostra se hai spiegato il tuo ragionamento in modo chiaro.