Un vertice madre in un grafo diretto G = (V, E) è un vertice v tale che tutti gli altri vertici G possono essere raggiunti da un percorso diretto da v Assegnare un algoritmo O (n + m) per verificare se il grafico G contiene un vertice materno.Come trovare il vertice madre in un grafico diretto in O (n + m)?
(c) da manuale Skiena
Trovato solo O (n (n + m)) modo
Quando googling ho effettivamente trovato la risposta here. Se questo è compito, dovresti pensarci due volte prima di sbirciare :)
Ho visto la soluzione. Non penso che abbiamo bisogno di trovare SCC. Basta fare un DFS da un vertice casuale e quindi fare il DFS dal vertice con l'ultima ora di fine. Se c'è un vertice materno allora deve essere questo.
step1. Ordinamento topologico dei vertici del grafico diretto.
step2. Ora controlliamo se possiamo raggiungere tutti i vertici del primo vertice dei vertici topologicamente filtrate in passaggio 1.
Per eseguire un passo 2, nuovamente inizializzare matrice scoperto [i] false e fare DFS startin dal primo nodo di topologicamente vertici ordinati.
Se tutti i vertici possono essere raggiunti, il grafico ha il vertice madre e il vertice madre sarà il primo dei vertici topologicamente ordinati.
complessità temporale: step1 prende O(n + m), passaggio 2 prende O(n + m) così totale O(n+m) + O(n+m) = O(n+m)
Algorithm ::
a) fare DFS/BFS del grafico e tenere traccia dell'ultimo vertice finito 'X' .
b) Se esiste un vertice madre, quindi 'x' è uno di questi. Verifica se 'x' è un vertice madre eseguendo DFS/BFS dal vertice 'x'.
Tempo complessità O (n + m) + O (n + m) = O (n + m)
sarà questo lavoro per il grafico seguente, se mi metto da B di vertice come casuale? A-> B B-> A A-> C A-> D – learner