Post-Auftrag Graph Traversal?

Question

Angesichts gerichteter Grafik unten, wie haben wir die Nachbestellung Traversal erreicht?

DFS

Vorbestellen: 1 2 5 4 6 3

Post-Order: 4 6 5 2 1 3

Answer 1

Post-Order-DFS hat im Wesentlichen die folgenden Entwurf:

1. Besuchen Sie die Kinder;
2. Besuchen Sie mich;

bei 1 Starten werden die Knoten in der folgenden Reihenfolge untersucht:

1 ->2 ->5 ->4(v) ->6(v) ->5(v) ->2(v) ->1(v) ->3(v)

Hier bedeutet (v), dass der Knoten jetzt besucht wird, nachdem er gesehen hat, dass entweder keines seiner Kinder nicht besucht wurde oder zumindest für einen Besuch in der Pipeline ist. Dies erklärt, warum die Traversierung 465213 ist.

Wahrscheinlich stört Sie, wie wir den Knoten 3 besucht haben, da ab 1 gibt es keinen Pfad zu 3. Die Antwort darauf scheint zu sein, dass nachdem der gesamte verbundene Graph gescannt wurde, der Traversalalgorithmus scannt, ob irgendwelche nicht-gescannten Knoten übrig sind. So endet es am Ende 3 am Ende zu besuchen.