Algoritmo per verificare se il grafo diretto è fortemente connesso

Question

Ho bisogno di verificare se un grafo 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 eseguire questa operazione è eseguire DFS e BFS su ogni nodo e vedere tutti gli altri sono ancora raggiungibili.

C'è un approccio migliore per farlo?

Answer 1

Tarjan's l'algoritmo di componenti fortemente connessi (o variazione Gabow's) sarà ovviamente sufficiente; se c'è solo un componente fortemente connesso, allora il grafico è fortemente connesso.

Entrambi sono orari lineari.

Come in una normale ricerca di profondità, si traccia lo stato di ciascun nodo: nuovo, visto ma ancora aperto (è nello stack di chiamate), visto e completato. Inoltre, si memorizza la profondità quando si raggiunge un nodo per la prima volta, e la profondità più bassa che è raggiungibile dal nodo (lo si conosce dopo aver terminato un nodo). Un nodo è la radice di un componente fortemente connesso se la profondità più bassa raggiungibile è uguale alla sua profondità. Questo 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, avviare il dfs da qualsiasi nodo singolo e, al termine, se la profondità minima raggiungibile è 0 e ogni nodo è stato visitato, quindi l'intero grafico è fortemente connesso

Answer 2

È possibile calcolare lo All-Pairs Shortest Path e vedere se uno è infinito.

Answer 3

Un modo per fare ciò sarebbe generare il Laplacian matrix per il grafico, quindi calcolare gli autovalori e infine contare il numero di zeri. Il grafico è fortemente connesso se esiste un solo autovalore zero.

Nota: Prestare attenzione al metodo leggermente diverso per la creazione della matrice Laplacian per i grafici diretti.

Answer 4

Algoritmo di Tarjan è già stato menzionato. Ma di solito trovo lo Kosaraju's Algorithm più facile da seguire anche se ha bisogno di due traversamenti del grafico. IIRC, è anche abbastanza ben spiegato in CLRS.

Answer 5

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 
} 

Answer 6

Considerare il seguente algoritmo.

---

1. Inizia un vertice casuale v del grafico G, ed eseguire un DFS(G, v).

   • Se DFS(G, v) riesce a raggiungere ogni altro vertice nel grafo G, allora c'è qualche vertice u, tale che non v'è alcun percorso orientato da v a u, e quindi G è non fortemente collegato.

   • Se raggiunge ogni vertice, esiste un percorso diretto da v a ogni altro vertice nel grafico G.

2. invertire la direzione di tutti gli spigoli del grafo orientato G.

3. Eseguire nuovamente un DFS a partire da v.

   • Se il DFS non riesce a raggiungere ogni vertice, allora c'è qualche vertice u, tale che nel grafico originale c'è alcun cammino orientato da u a v.

   • D'altra parte, se lo fa raggiungere ogni vertice, poi nel grafico originale v'è un percorso diretto da ogni vertice u a v.

Pertanto, se G "passa" sia DFSS, è fortemente collegato. Inoltre, poiché un DFS viene eseguito nel tempo O(n + m), questo algoritmo viene eseguito nel tempo O(2(n + m)) = O(n + m), poiché richiede 2 traversamenti DFS.