Algoritmo per verificare se il grafico diretto è fortemente connesso

StackOverflow https://stackoverflow.com/questions/1434787

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?

È stato utile?

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.

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

    • Se u non riesce a raggiungere tutti gli altri vertici nel grafico DFS, allora c'è qualche vertice O(n + m), tale che non esiste un percorso diretto da O(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 <=>.

  2. Inverti la direzione di tutti i bordi nel grafico diretto <=> .

  3. 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.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top