Componenti fortemente connesse con Kosaraju

Una componente fortemente connessa (SCC) di un grafo orientato è un insieme massimale di nodi tale che esiste un percorso da ogni nodo a ogni altro nodo dell'insieme. Ad esempio, se i nodi A, B e C formano un ciclo (A→B→C→A), appartengono tutti alla stessa SCC. Un singolo nodo senza un self-loop costituisce una SCC a sé. Le SCC rivelano la struttura ciclica di un grafo orientato.

L'algoritmo di Kosaraju's trova tutte le SCC in O(V + E) utilizzando due passaggi DFS. Passaggio 1: esegua la DFS sul grafo originale e inserisca i nodi in uno stack secondo il loro ordine di completamento, cioè in post-order. Passaggio 2: esegua la DFS sul grafo trasposto, cioè invertito, elaborando i nodi in ordine inverso rispetto al completamento, estraendoli dallo stack. Ogni albero DFS del passaggio 2 corrisponde a una SCC.

Nel passaggio 1, la SCC il cui albero DFS termina per ultimo è quella senza archi uscenti verso altre SCC, cioè una SCC "pozzo" nel DAG di condensazione. Nel grafo trasposto, questa SCC non ha archi entranti da altre SCC, quindi la DFS avviata da essa rimane confinata al suo interno durante il passaggio 2. Ogni DFS successiva del passaggio 2 rimane all'interno della propria SCC, perché tutti gli archi tra SCC sono stati invertiti e conducono verso SCC già visitate.

Esegua la DFS sul grafo originale e inserisca ogni nodo in uno stack dopo averlo completato, cioè in post-order. In questo passaggio non ci interessano le componenti, ma solo l'ordine di completamento. L'ultimo nodo a terminare apparterrà a una SCC "sorgente" del DAG di condensazione.

Estragga i nodi dallo stack dei completamenti, iniziando dal tempo di completamento maggiore, ed esegua la DFS sul grafo trasposto. Ogni DFS avviata da un nodo non visitato scopre esattamente una SCC. Contrassegni tutti i nodi raggiunti da questa DFS come appartenenti alla stessa componente.

Il grafo trasposto inverte ogni arco: se il grafo originale contiene u → v, il trasposto contiene v → u. La trasposizione preserva le SCC: se A e B appartengono alla stessa SCC nel grafo originale, rimangono nella stessa SCC anche nel trasposto, perché tutti i percorsi vengono invertiti ma continuano a collegare i nodi. Costruire il trasposto durante l'analisi dell'input, come mostrato sopra, evita un passaggio di trasposizione separato.

Per i grafi grandi, si sostituisca la DFS ricorsiva con una DFS iterativa che utilizza uno stack esplicito, così da evitare il limite di ricorsione di Python. La versione iterativa inserisce i nodi nello stack, li elabora e mantiene un marcatore separato di «ritorno» per simulare l'ordine posticipato.

Algoritmo di Tarjan trova le SCC in un'unica passata DFS, rispetto alle due passate di Kosaraju. Mantiene uno stack di nodi e assegna a ogni nodo un tempo di scoperta e un valore low-link. Quando il tempo di scoperta di un nodo è uguale al suo low-link, quel nodo è la radice di una SCC. L'algoritmo di Tarjan è leggermente più complesso da implementare, ma evita di costruire il grafo trasposto. Entrambi hanno complessità O(V + E).

Le SCC vengono utilizzate per: (1) Ottimizzazione dei compilatori — individuare le funzioni ricorsive reciproche. (2) Analisi delle reti sociali — trovare comunità strettamente interconnesse. (3) Problema 2-SAT — determinare la soddisfacibilità di clausole con 2 letterali. (4) Web crawling — individuare gruppi di pagine con molti collegamenti incrociati. (5) DAG di condensazione — dopo aver trovato le SCC, la condensazione del grafo è un DAG, che consente di analizzare topologicamente grafi ciclici.

La condensazione di un grafo orientato contrae ogni SCC in un singolo nodo e aggiunge un arco tra due supernodi se esiste un arco tra le rispettive SCC costituenti. Il risultato è sempre un DAG, sul quale è possibile eseguire un ordinamento topologico. Questo consente di applicare ai grafi orientati generali algoritmi che funzionano solo sui DAG, come la programmazione dinamica, lavorando sulla loro condensazione.

Il numero di SCC in un grafo orientato rivela la sua struttura ciclica. Un DAG ha n SCC, poiché ogni nodo costituisce una SCC distinta. Un grafo fortemente connesso ha esattamente 1 SCC. In generale, dopo la condensazione, le SCC formano un DAG: il grafo di condensazione. Se il DAG di condensazione ha un'unica sorgente, cioè un nodo con grado entrante 0, e un'unico pozzo, cioè un nodo con grado uscente 0, nel grafo di condensazione valgono determinate proprietà di connettività. Queste proprietà vengono verificate nei problemi di raggiungibilità dopo l'aggiunta di un numero minimo di archi.

In questa lezione ha imparato che: le SCC sono insiemi massimali in cui ogni nodo è raggiungibile da tutti gli altri, Kosaraju utilizza due passate DFS — la prima sul grafo originale per determinare l'ordine di completamento, la seconda sul grafo trasposto e la condensazione di qualsiasi grafo orientato è un DAG utilizzabile per ulteriori analisi. Nella prossima lezione costruiremo strutture dati TrieNode per le operazioni di inserimento, ricerca e gestione dei prefissi.