DFS rekursiv vs DFS iterativ

Ich versuche, den Unterschied zwischen DFS rekursiv und DFS iterativ zu verstehen. Verwendet der mit dem Stack einen iterativen oder rekursiven Ansatz?DFS rekursiv vs DFS iterativ

Zum Beispiel, was wäre die Ausgabe von einer rekursiven DFS-Traversal des Graphen und eine DFS iterative Traversal des Graphen zu verwenden? Die Nachbarn werden in alphabetischer Reihenfolge durchlaufen.

Heres der Graph:

enter image description here

Für eine DFS-Traversal (der mit einem Stapel, nicht sicher, ob seine rekursive oder iterative) das ist, was ich habe: A, C, D, E, F. Kann jemand bestätigen, welche Art von DFS-Traversal dies ist und wie der andere funktionieren würde? Vielen Dank!

Quelle

2014-11-20 BostonMan

Übrigens ist es besser, diese Art von Frage zu stellen: http://cs.stackexchange.com/. –

Nach meinem Verständnis unterscheiden sich die rekursive und iterative Version nur in der Verwendung des Stapels. Die rekursive Version verwendet den Aufrufstapel, während die iterative Version genau dieselben Schritte ausführt, jedoch einen benutzerdefinierten Stapel anstelle des Aufrufstapels verwendet. Es gibt keinen Unterschied in der Abfolge der Schritte selbst (wenn geeignete Anknüpfungsregeln verwendet werden, um eine gleiche Traversierungssequenz für untergeordnete Knoten sicherzustellen - falls gewünscht), so ist es unmöglich, die Ausgabe zu überprüfen, um zu entscheiden, ob eine iterative oder rekursive Implementierung verwendet wurde .

Quelle

2014-11-20 07:27:40 Codor

Dies ist nicht ganz richtig. Es gibt Unterschiede in der Ausgabe zwischen rekursiven und iterativen Ansätzen. Siehe [Iterative DFS vs Recursive DFS und verschiedene Elemente Reihenfolge] (http://Stackoverflow.com/q/9201166/572670) für Details – amit

Nun, Sie haben Recht, aber wie in der verknüpften Frage erwähnt, an sich die Reihenfolge, in der Kinder durchlaufen sind nicht spezifiziert; einige zusätzliche Aufträge müssten definiert werden. Ich werde meine Antwort ein wenig ändern. – Codor

Wie in der anderen Antwort angegeben, werden beim Durchsuchen des Diagramms mit DFS die Scheitelpunkte auf die gleiche Weise unabhängig von der tatsächlichen DFS-Implementierung mit Iteration oder Rekursion aufgerufen. Siehe Pseudocode auf der Wikipedia article.

Sie haben eine zusätzliche Anforderung, die benachbarten Knoten in alphabetischer Reihenfolge zu besuchen. Das bedeutet, dass der Stack sortiert werden muss, wenn man ihn in die iterative Version verschiebt, oder dass man die benachbarten Knoten in sortierter Reihenfolge rekursiv behandelt (in der rekursiven Version). Beide Implementierungen werden sich genau gleich verhalten.

Angesichts der Einschränkung der alphabetischen Reihenfolge ist das Ergebnis A, C, D, E, F die einzig mögliche DFS-Traversierung Ihres Graphen.

Quelle

2014-11-20 08:45:22

Antwort

Verwandte Themen