L'algoritmo SCC di Tarjan fornisce un tipo topologico di SCC?

Question

Sto studiando SCC e algoritmi su di loro, e ho visto che la gente quasi sempre menziona che l'algoritmo di Kosaraju trova l'SCC e gli dà anche ordinato in un tipo topologico (invertito).

La mia domanda è: l'algoritmo di Tarjan non trova anche un ordinamento topologico (invertito)? Ho scoperto che non è menzionato (almeno da dove ho letto, eccetto wikipedia).

Ci ho pensato e ho perfettamente senso. Quando tarjans_dfs viene chiamato su qualche nodo u, tutti gli SCC raggiungibili da te verranno trovati prima del tuo SCC. Ho sbagliato?

Wikipedia dice che in realtà non trovarlo:

"Mentre non v'è niente di speciale l'ordine dei nodi all'interno ogni componente fortemente connessa, una proprietà utile del algoritmo è che nessun componente fortemente connessa sarà identificato prima di uno qualsiasi dei suoi successori Pertanto, l'ordine in cui i componenti fortemente collegati sono identificati costituisce un tipo di topologia inverso del DAG formato dai componenti fortemente collegati. "

È una mia idea, o è molto più noto che l'algoritmo di Kosaraju trova l'ordine topologico rispetto al fatto che anche Tarjan lo fa?

Answer 1

sì, l'ho usato e mi è venuta la stessa domanda.

In realtà non ho avuto il tempo di dimostrarlo ma ogni test case (molte migliaia) restituisce sempre un grafico condensato topologico ordinato.

Answer 2

Sì, lo fa. L'algoritmo SCC di Tarjan funziona eseguendo un DFS su un grafico e tenendo traccia delle radici degli SCC in una pila. Un metodo per trovare un ordinamento topologico è eseguire un DFS su un grafico e tenere traccia dell'ordine di uscita. L'ordine di uscita di questi nodi nell'algoritmo SCC di Tarjan fornisce un ordinamento topologico.

Donald Knuth menziona addirittura in an interview quando si parla di algoritmo di SCC di Tarjan, che, dice, è uno dei suoi preferiti:

Le strutture di dati che ha ideato per questo problema si incastrano in un modo incredibilmente bella, così che le quantità che devi guardare mentre esplori un grafico diretto sono sempre magicamente a portata di mano. E il suo algoritmo esegue anche l'ordinamento topologico come sottoprodotto.

Answer 3

Sì. Dato che Tarjan è basato su Depth First Search, tutto ciò che devi fare è aggiungere i vertici alla cima di una lista quando ogni vertice raggiunge lo stato "chiuso" (cioè la sua chiamata dfs/tarjan termina per quel vertice)

Ecco un esempio C/C++/Pseudo-Code:

void tarjan(int u) { 
    visited[u] = true; 
    closed[u] = false; 
    //dfs + tarjan processing 
    for (vi v = G[u].begin(); v != G[u].end(); v++) { 
     if (!visited[*v]) { 
      dfs(*v); 
     } else if (!closed[*v]) { 
      // has Cycle 
     } 
    } 
    closed[u] = true; 
    //add u to the top of your list here 
}