Ich weiß, dass die übliche Art, eine topologische Sortierung durchzuführen, die Verwendung von DFS mit Rekursion ist. Aber wie würdest du es mit stack<int> anstelle von Rekursion machen? Ich muss die umgekehrte Nachbestellung erhalten, aber ich bin irgendwie fest:
Das Diagramm ist eine vector<vector<int> > Adjazenzliste
Das Folgende ist das DFS, das ich für die topologische Sortierung verwenden möchte
%Vor% Um die postOrder Liste zu erstellen, müssen Sie wissen, wann Ihr Algorithmus das letzte Kind des Knotens k fertig bearbeitet hat.
Eine Möglichkeit, herauszufinden, wann Sie das letzte Kind vom Stapel entfernt haben, besteht darin, Sondermarken auf den Stapel zu setzen, um anzuzeigen, wo die Kinder eines bestimmten Knotens beginnen. Du könntest den Typ deines dfs Stacks in vector<pair<bool,int> > ändern. Wenn bool auf true festgelegt ist, wird ein Elternelement angegeben. false zeigt ein Kind an.
Wenn Sie ein "untergeordnetes Paar" (dh eines mit dem ersten Mitglied des Paares auf false ) vom Stapel entfernen, führen Sie den Code aus, den Sie gerade haben, dh schieben Sie alle Ihre Kinder mit Ihrem auf den Stapel for Schleife. Bevor Sie die for -Schleife eingeben, sollten Sie jedoch make_pair(true, node) auf den Stapel schieben, um den Anfang aller untergeordneten Elemente dieses node zu markieren.
Wenn Sie ein "Elternpaar" aus dem Stapel entfernen, schieben Sie den übergeordneten Index auf postOrder und ziehen weiter:
Ich denke, Ihr Code ist ein gutes nicht-rekursives DFS. Der springende Punkt der topologischen Sortierung ist:
Wenn Sie einen Knoten auswählen, um ihn in den Stapel zu schieben. Dieser Knoten darf keinen Prozessor haben (hat einen In-Grad von 0). Das bedeutet, dass Sie eine DFS-Basis auf In-Grad ausführen, statt alle benachbarten Knoten in den Stapel zu schieben, wählen Sie immer den mit 0 in Grad aus
Sie drücken also jeden Knoten, der keinen Vorgänger im Stapel hat. Öffnen Sie eins, drucken Sie es aus und entfernen Sie es aus der Liste aller benachbarten Knoten (oder verringern Sie die Anzahl der benachbarten Knoten in Grad um 1). Sie müssen Ihre angrenzende Liste bearbeiten. Dann schiebe alle seine benachbarten Knoten mit dem Grad 0 jetzt in den Stapel (diese Phase kann fehlschlagen, aber kein Problem, du hast immer noch einige Knoten im Stapel). Dann öffne den nächsten. Wiederholen Sie dies, bis der Stapel leer ist. Die von Ihnen gedruckte Knotensequenz ist das topologische Sortierergebnis des Diagramms.
Der Knoten wird zum ersten Mal besucht und ist noch in Bearbeitung. Er wird als falsch zum Stack hinzugefügt. Diese Knoten werden dann vom Stapel als LIFO verarbeitet und in wahr geändert (verarbeitet bedeutet, dass Kinder besucht werden). Nachdem alle Kinder verarbeitet wurden, während der Pfad zurückverfolgt wurde, fiel dieser Knoten vom Stapel.
Für diejenigen, die versuchen, diesen Code zu implementieren, sollte visited[node.second]=true; an die 2 Stellen verschoben werden, an denen Knoten 1 hinzugefügt wurde, um als false zu stapeln. Dies, so dass Rückkanten, die zu bereits verfolgten Vertices führen, nicht erneut betrachtet werden.
Unten ist mein iterativer Code zur topologischen Sortierung von DAG.
%Vor%Zum Testen: ideone
Hoffe das hilft!
Hier gehen wir wieder. :-) Ich unterbreite eine Antwort, weil ich nicht genügend Punkte habe, um Kommentare abzugeben. : - (
Nun, lassen Sie mich sagen, dass ich diesen Algorithmus sehr mag. Wenn der Graph richtig definiert ist, liegt kein Fehler vor. Aber nimm dieses Diagramm:
%Vor%Dies wird angezeigt: 2 1 2 0
Um sich vor Graphen zu schützen, die auf diese Weise definiert sind oder bei denen die Kanten zufällig sind, können Sie dies tun:
%Vor%Oder Sie könnten die Grafik vorbestellen, vielleicht könnte jemand diese Lösung zeigen. Wie man zufällig gegebene Ränder vorbestellt, die keine zweite Prüfung benötigen. : -)
Und ich tat es über den Atif Hussain Kommentar und es ist falsch. Das würde nie funktionieren. Sie möchten den Stapel immer so lange wie möglich nach unten drücken, damit er so schnell wie möglich erscheint.
Tags und Links algorithm c++ stack depth-first-search topological-sort