In un grafo non orientato la connessione è semplice: due vertici sono nella stessa componente se esiste un cammino tra loro. Nei grafi orientati le cose si complicano, perché poter andare da A a B non significa poter tornare da B ad A. Una pagina web può rimandare a un'altra senza essere a sua volta citata; un modulo software può importarne un altro senza esserne importato.
Le componenti fortemente connesse (in inglese SCC, Strongly Connected Components) rispondono alla domanda giusta per i grafi orientati: quali gruppi di vertici sono tutti mutuamente raggiungibili?
Definizione
Due vertici u e v sono fortemente connessi se esiste un cammino orientato da u a v e anche uno da v a u. Questa relazione è riflessiva, simmetrica e transitiva, quindi divide i vertici in classi: le componenti fortemente connesse.
Esempi:
- in un grafo di dipendenze tra moduli, una SCC con più di un elemento è un gruppo di moduli che si importano a vicenda in modo circolare;
- in una rete di account che si trasferiscono denaro, una SCC è un gruppo in cui il denaro può circolare e tornare al punto di partenza;
- in un automa, una SCC è un insieme di stati da cui si può uscire ma in cui, una volta tornati, si può girare indefinitamente.
Il grafo condensato
Se si contrae ogni SCC in un unico «supervertice», mantenendo gli archi tra componenti diverse, si ottiene il grafo condensato. Questo grafo è sempre un DAG: se ci fosse un ciclo tra due componenti, i loro vertici sarebbero mutuamente raggiungibili e quindi apparterrebbero alla stessa componente.
È un risultato molto pratico. Molti problemi difficili sui grafi con cicli diventano semplici sui DAG, grazie all'ordinamento topologico. La strategia standard è quindi: trovare le SCC, risolvere il problema dentro ogni componente (dove tutto è raggiungibile da tutto), poi propagare i risultati sul DAG condensato in ordine topologico.
L'algoritmo di Kosaraju
È il più facile da capire e richiede due visite in profondità.
- Esegui una DFS completa sul grafo e annota l'ordine in cui i vertici finiscono.
- Costruisci il grafo trasposto, invertendo il verso di ogni arco.
- Esegui DFS sul grafo trasposto, prendendo i vertici di partenza in ordine di fine decrescente. Ogni visita lanciata in questa fase raggiunge esattamente una componente fortemente connessa.
Perché funziona? Il vertice che finisce per ultimo nella prima DFS appartiene a una componente «sorgente» del DAG condensato, da cui non si torna indietro. Nel grafo trasposto questa componente diventa un «pozzo»: partendo da lì, la visita non può uscire e raccoglie solo la sua componente. Si procede poi con la componente successiva nell'ordine, e così via.
Il costo è proporzionale a n + m, con il prezzo di dover costruire e memorizzare anche il grafo trasposto.
L'algoritmo di Tarjan
Tarjan trova le stesse componenti con una sola DFS, senza grafo trasposto. Per ogni vertice tiene due valori:
- indice: l'ordine di scoperta;
- lowlink: il più piccolo indice raggiungibile dal sottoalbero del vertice, usando archi d'albero e al massimo un arco verso un vertice ancora sulla pila.
I vertici vengono inseriti in una pila man mano che sono scoperti. Quando, alla fine della visita di un vertice v, risulta lowlink[v] = indice[v], v è la «radice» di una componente: si estraggono dalla pila tutti i vertici fino a v compreso, e quelli formano la componente.
def tarjan(adj, n):
indice, low = [None] * n, [0] * n
sulla_pila, pila, componenti = [False] * n, [], []
contatore = [0]
def visita(v):
indice[v] = low[v] = contatore[0]; contatore[0] += 1
pila.append(v); sulla_pila[v] = True
for w in adj[v]:
if indice[w] is None:
visita(w)
low[v] = min(low[v], low[w])
elif sulla_pila[w]:
low[v] = min(low[v], indice[w])
if low[v] == indice[v]:
comp = []
while True:
w = pila.pop(); sulla_pila[w] = False
comp.append(w)
if w == v: break
componenti.append(comp)
for v in range(n):
if indice[v] is None:
visita(v)
return componenti
Anche Tarjan costa n + m. Un dettaglio utile: le componenti vengono prodotte in ordine topologico inverso del grafo condensato, quindi spesso non serve un ordinamento aggiuntivo. Su grafi grandi va riscritto in forma iterativa per evitare di superare il limite di ricorsione.
Confronto
| Aspetto | Kosaraju | Tarjan |
|---|---|---|
| Visite DFS | due | una |
| Grafo trasposto | necessario | non necessario |
| Facilità di comprensione | alta | media |
| Ordine delle componenti | topologico | topologico inverso |
Un'applicazione elegante: 2-SAT
Un problema di 2-SAT chiede di assegnare vero o falso a delle variabili rispettando clausole del tipo «x oppure non y». Ogni clausola diventa due implicazioni, e quindi due archi in un grafo di implicazioni. La formula è soddisfacibile se e solo se nessuna variabile si trova nella stessa SCC della propria negazione. Le componenti forniscono anche un'assegnazione valida. Così un problema logico si risolve in tempo lineare con una visita di grafo.
In sintesi
- Nei grafi orientati, una SCC raccoglie i vertici mutuamente raggiungibili.
- Contraendo le SCC si ottiene sempre un DAG, su cui molti problemi diventano semplici.
- Kosaraju usa due DFS e il grafo trasposto; è il più intuitivo.
- Tarjan usa una sola DFS con indici e lowlink; produce le componenti in ordine topologico inverso.
- Entrambi costano n + m e risolvono, tra l'altro, il problema del 2-SAT.
