Algorytm znajdowania ścieżki Hamiltona w DAG

Question

Mam na myśli Księgę Skienna na temat algorytmów.

Problem testowania czy wykres G zawiera Hamiltonian path jest NP-hard, gdzie Hamiltonian ścieżka P jest ścieżka, która odwiedza każdy wierzchołek dokładnie raz. Nie musi być krawędzi G od wierzchołka końcowego do początkowego wierzchołka P, w przeciwieństwie do problemu z cyklem Hamiltona.

Biorąc pod uwagę skierowany wykres acykliczny G (DAG), należy podać algorytm czasowy O(n + m), aby sprawdzić, czy zawiera ścieżkę hamiltonowską.

Moje podejście,

Mam zamiar użyć DFS i Topological sorting. Ale nie wiedziałem, jak połączyć te dwie koncepcje w rozwiązywaniu problemu. W jaki sposób można użyć sortowania topologicznego do określenia rozwiązania.

Wszelkie sugestie?

Answer 1

Możesz najpierw topologicznie posortować DAG (każdy DAG może być sortowany topologicznie) w O (n + m).

Po wykonaniu tej czynności wiesz, że krawędź przechodzi od niższych wierzchołków indeksu do wyższych. Oznacza to, że istnieje ścieżka hamiltonska wtedy i tylko wtedy, gdy istnieje krawędź pomiędzy kolejnymi wierzchołkami, np.

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

(To dlatego, że w ścieżki Hamiltona nie można „cofnąć”, a jeszcze trzeba odwiedzić wszystkich, więc jedynym sposobem jest „nie pominąć”)

Można to sprawdzić warunek w O (n).

Tak więc ogólna złożoność to O (m + n).

Answer 2

Nie sądzę, że oświadczenie @agassaa jest całkowicie poprawne. Rozważ prosty przykład, w którym występują trzy węzły "A", "B", "C" i krawędzie A-> B, B-> C, A-> C. Podczas gdy A ma dwoje dzieci, a C ma dwoje rodziców, A-> B-> C tworzy ścieżkę hamiltonowską. Nie musisz przechodzić przez każdą krawędź na wykresie, aby ścieżka była hamiltonianem.

A DAG that has Hamiltonian cycle