Algorithmus zum Finden eines Hamilton-Pfades in einem DAG

Question

Ich beziehe mich auf Skiennas Buch über Algorithmen.

Das Problem der Prüfung, ob ein Graph G ein Hamiltonian path enthält NP-hard ist, wobei ein Hamilton-Pfad P ist ein Weg, die jeden Scheitelpunkt genau einmal besucht. Es muss keine Kante in G von dem Endscheitelpunkt zu dem Anfangsscheitelpunkt von P geben, anders als in dem Hamilton-Zyklus-Problem.

Bei einem gerichteten azyklischen Graphen G (DAG), eine O(n + m) Algorithmus geben zu prüfen, ob es eine Hamilton-Pfad enthält.

Mein Ansatz,

Ich plane DFS und Topological sorting zu verwenden. Aber ich wusste nicht, wie ich die beiden Konzepte verbinden sollte, um das Problem zu lösen. Wie kann eine topologische Sortierung zur Bestimmung der Lösung verwendet werden?

Irgendwelche Vorschläge?

Answer 1

Sie können die DAG zuerst topologisch sortieren (jede DAG kann topologisch sortiert sein) in O (n + m).

Sobald dies erledigt ist, wissen Sie, dass die Kante von unteren Indexscheitelpunkten zu höheren geht. Dies bedeutet, dass es einen Hamilton-Pfad gibt, wenn und nur wenn zwischen aufeinanderfolgenden Eckpunkten eine Kante vorhanden ist, z.

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

(Dies liegt daran, in einem Hamilton-Pfad kann man nicht „zurückgehen“, und doch haben Sie alle zu besuchen, so dass der einzige Weg ist, um „nicht überspringen“)

Sie können dies überprüfen Bedingung in O (n).

Somit ist die Gesamtkomplexität O (m + n).

Answer 2

Ich glaube nicht, dass die Aussage von @agassaa völlig korrekt ist. Betrachten Sie das einfache Beispiel, wo drei Knoten "A", "B", "C" und Kanten A -> B, B -> C, A -> C sind. Während A zwei Kinder hat und C zwei Eltern hat, bildet A-> B-> C einen Hamilton-Pfad. Sie müssen nicht jede Kante im Diagramm durchlaufen, damit der Pfad Hamiltonoperativ ist.

A DAG that has Hamiltonian cycle