Algoritmo per trovare un percorso Hamilton in un DAG

Question

Mi riferisco al libro sugli algoritmi di Skienna.

Il problema di verificare se un grafo G contiene un Hamiltonian path è NP-hard, dove un percorso hamiltoniano P è un percorso che visita ogni vertice esattamente una volta. Non deve esserci un margine in G dal vertice finale al vertice di partenza di P, diversamente dal problema del ciclo di Hamiltoniana.

Dato un grafico aciclico diretto G (DAG), fornire un algoritmo tempo O(n + m) per verificare se contiene o meno un percorso hamiltoniano.

Il mio approccio,

Sto progettando di utilizzare DFS e Topological sorting. Ma non sapevo come collegare i due concetti per risolvere il problema. Come si può usare un ordinamento topologico per determinare la soluzione.

Qualche suggerimento?

Answer 1

È possibile prima ordinare topologicamente il DAG (ogni DAG può essere ordinato topologicamente) in O (n + m).

Una volta eseguita questa operazione, si sa che il bordo passa dai vertici dell'indice più bassi a quelli più alti. Ciò significa che esiste un percorso hamiltoniano se e solo se vi sono spigoli tra vertici consecutivi, ad es.

(1,2), (2,3), ..., (n-1,n). 

(Questo perché in un percorso hamiltoniano non si può "tornare indietro" e ancora si deve visitare tutti, quindi l'unico modo è quello di "non saltare")

È possibile controllare questo condizione in O (n).

Pertanto, la complessità complessiva è O (m + n).

Answer 2

Non penso che la dichiarazione di @agassaa sia completamente corretta. Considera il semplice esempio in cui ci sono tre nodi "A", "B", "C" e bordi A-> B, B-> C, A-> C. Mentre A ha due figli e C ha due genitori, A-> B-> C forma un percorso hamiltoniano. Non è necessario attraversare tutti i bordi del grafico perché il percorso sia hamiltoniano.

A DAG that has Hamiltonian cycle