Algoritmo per verificare se il grafico diretto è fortemente connesso
-
07-07-2019 - |
Domanda
Devo verificare se un grafico diretto è fortemente connesso o, in altre parole, se tutti i nodi possono essere raggiunti da qualsiasi altro nodo (non necessariamente attraverso il bordo diretto).
Un modo per farlo è eseguire un DFS e un BFS su ogni nodo e vedere tutti gli altri sono ancora raggiungibili.
Esiste un approccio migliore per farlo?
Soluzione
Tarjan's algoritmo di componenti fortemente connessi (o la variazione di Gabow ) sarà ovviamente sufficiente; se esiste un solo componente fortemente connesso, il grafico è fortemente connesso.
Entrambi sono tempi lineari.
Come con una prima ricerca di profondità normale, segui lo stato di ciascun nodo: nuovo, visto ma ancora aperto (è nello stack di chiamate), e visto e finito. Inoltre, memorizzi la profondità quando hai raggiunto un nodo per la prima volta, e la profondità più bassa che è raggiungibile dal nodo (lo sai dopo aver finito un nodo). Un nodo è la radice di un componente fortemente connesso se la profondità raggiungibile più bassa è uguale alla propria profondità. Funziona anche se la profondità con cui si raggiunge un nodo dalla radice non è il minimo possibile.
Per verificare solo se l'intero grafico è un singolo SCC, avvia dfs da qualsiasi singolo nodo e, quando hai finito, se la profondità raggiungibile più bassa è 0 e ogni nodo è stato visitato, allora l'intero grafico è fortemente connesso.
Altri suggerimenti
Considera il seguente algoritmo.
-
Inizia da un vertice casuale
v
del graficoG
ed esegui unDFS(G, v)
.-
Se
u
non riesce a raggiungere tutti gli altri vertici nel graficoDFS
, allora c'è qualche verticeO(n + m)
, tale che non esiste un percorso diretto daO(2(n + m)) = O(n + m)
a <=>, e quindi <=> non è fortemente connesso . -
Se raggiunge tutti i vertici, allora c'è un percorso diretto da <=> a tutti gli altri vertici nel grafico <=>.
-
Inverti la direzione di tutti i bordi nel grafico diretto <=> .
-
Esegui di nuovo un <=> a partire da <=>.
-
Se il DFS non riesce a raggiungere tutti i vertici, allora c'è qualche vertice <=>, tale che nel grafico originale non esiste un percorso diretto da <=> a <=>.
-
D'altra parte, se raggiunge tutti i vertici, nel grafico originale esiste un percorso diretto da ogni vertice da <=> a <=> .
-
Quindi, se G " passa " entrambi i DFS, è fortemente connesso. Inoltre, poiché un DFS viene eseguito in <=> tempo, questo algoritmo viene eseguito in <=> tempo, poiché richiede 2 attraversamenti DFS.
Per verificare se ogni nodo ha entrambi i percorsi verso e da ogni altro nodo in un dato grafico:
1. DFS / BFS da tutti i nodi:
Algoritmo di Tarjan suppone che ogni nodo abbia una profondità d[i]
. Inizialmente, la radice ha la profondità più piccola. E eseguiamo gli aggiornamenti DFS post ordine d[i] = min(d[j])
per tutti i vicini j
di i
. In realtà BFS funziona bene anche con la regola di riduzione u
qui.
function dfs(i)
d[i] = i
mark i as visited
for each neighbor j of i:
if j is not visited then dfs(j)
d[i] = min(d[i], d[j])
Se esiste un percorso di inoltro da v
a d[u] <= d[v]
, quindi d[v] <= d[u] <= d[v]
. In SCC, <=>, quindi, tutti i nodi in SCC avranno la stessa profondità. Per sapere se un grafico è un SCC, controlliamo se tutti i nodi hanno lo stesso <=>.
2. Due DFS / BFS dal singolo nodo:
È una versione semplificata dell ' Kosaraju & # 8217; s algoritmo . A partire dalla radice, controlliamo se ogni nodo può essere raggiunto da DFS / BFS. Quindi, invertire la direzione di ogni bordo. Controlliamo se ogni nodo può essere nuovamente raggiunto dalla stessa radice. Vedi codice C ++ .
Puoi calcolare il Percorso più breve per tutte le coppie e vedere se c'è infinito .
L'algoritmo di Tarjan è già stato menzionato. Ma di solito trovo l'algoritmo di Kosaraju più facile da seguire anche se necessita di due traversate del grafico . IIRC, è anche abbastanza ben spiegato in CLRS.
test-connected(G)
{
choose a vertex x
make a list L of vertices reachable from x,
and another list K of vertices to be explored.
initially, L = K = x.
while K is nonempty
find and remove some vertex y in K
for each edge (y, z)
if (z is not in L)
add z to both L and K
if L has fewer than n items
return disconnected
else return connected
}
Un modo per farlo sarebbe quello di generare la matrice laplaciana per il grafico, quindi per il grafico, quindi calcola gli autovalori e infine conta il numero di zeri. Il grafico è fortemente connesso se esiste un solo autovalore zero.
Nota: presta attenzione al metodo leggermente diverso per la creazione della matrice laplaciana per i grafici diretti.
Puoi usare Kosaraju & # 8217; s Un semplice algoritmo basato su DFS che esegue due traversate DFS del grafico:
L'idea è che se ogni nodo può essere raggiunto da un vertice v e ogni nodo può raggiungere v, il grafico è fortemente connesso. Nel passaggio 2 dell'algoritmo, controlliamo se tutti i vertici sono raggiungibili da v. Nel passaggio 4, controlliamo se tutti i vertici possono raggiungere v (Nel grafico inverso, se tutti i vertici sono raggiungibili da v, quindi tutti i vertici possono raggiungere v in originale grafico).
Algoritmo: 1) Inizializza tutti i vertici come non visitati.
2) Esegui un attraversamento DFS del grafico a partire da qualsiasi vertice arbitrario v. Se l'attraversamento DFS non & # 8217; t visita tutti i vertici, quindi restituisce false.
3) Invertire tutti gli archi (o trovare trasporre o invertire il grafico)
4) Contrassegna tutti i vertici come non visitati nel grafico invertito.
5) Esegui un attraversamento DFS del grafico invertito a partire dallo stesso vertice v (uguale al passaggio 2). Se l'attraversamento DFS non & # 8217; t visita tutti i vertici, quindi restituisce false. Altrimenti restituisce true.
Complessità temporale: la complessità temporale dell'implementazione precedente è la stessa della prima ricerca della profondità che è O (V + E) se il grafico è rappresentato usando la rappresentazione dell'elenco di adiacenza.