Ich habe SCC und Algorithmen über sie studiert, und ich habe gesehen, dass Leute fast immer erwähnen, dass der Algorithmus von Kosaraju den SCC findet und sie auch in einer (umgekehrten) topologischen Reihenfolge sortiert.
Meine Frage ist: Findet Tarjans Algorithmus auch keine (umgekehrte) topologische Sortierung? Ich habe festgestellt, dass es nicht erwähnt wird (zumindest von wo ich gelesen habe, außer Wikipedia).
Ich habe darüber nachgedacht und vollkommen Sinn gemacht. Wenn tarjans_dfs auf einem Knoten u aufgerufen wird, werden alle SCCs, die von u erreichbar sind, vor dem SCC von u gefunden. Liege ich falsch?
Wikipedia sagt, dass es es tatsächlich findet:
"Während die Reihenfolge der Knoten darin nichts Besonderes ist jede stark verbundene Komponente, eine nützliche Eigenschaft der Algorithmus ist, dass keine stark verbundene Komponente identifiziert wird vor irgendeinem seiner Nachfolger. Daher die Reihenfolge, in der die stark verbundene Komponenten werden identifiziert, bildet eine Umkehrung topologische Art der DAG gebildet von der stark verbunden Komponenten. "
Ist es meine Idee, oder ist es viel bekannter, dass der Algorithmus von Kosaraju die topologische Ordnung findet, als die Tatsache, dass Tarjan es auch tut?
Ja, tut es. Tarjans SCC-Algorithmus funktioniert, indem er ein DFS auf einem Graphen ausführt und die Wurzeln der SCCs auf einem Stapel verfolgt. Eine Methode, um eine topologische Sortierung zu finden, besteht darin, ein DFS auf einem Graphen auszuführen und die Reihenfolge der Ausgänge zu verfolgen. Die Austrittsreihenfolge dieser Knoten in Tarjans SCC-Algorithmus liefert eine topologische Sortierung.
Donald Knuth erwähnt sogar in einem Interview , wenn er darüber spricht Tarjans SCC-Algorithmus, von dem er sagt, ist einer seiner Favoriten:
Die Datenstrukturen, die er für dieses Problem entwickelt hat, passen erstaunlich gut zusammen, so dass die Mengen, die Sie beim Erkunden eines gerichteten Graphen sehen müssen, immer magisch zur Hand sind. Und sein Algorithmus führt auch eine topologische Sortierung als Nebenprodukt durch.
Ja. Da Tarjan auf der Tiefensuche basiert, müssen Sie die Scheitelpunkte nur an den Anfang einer Liste setzen, wenn jeder Scheitelpunkt den "geschlossenen" Zustand erreicht (dh sein dfs / tarjan-Aufruf endet für diesen Scheitelpunkt)
Hier ist ein C / C ++ / Pseudocode-Beispiel:
%Vor%es tut, ich habe es verwendet und die gleiche Frage kam mir in den Sinn.
Ich hatte tatsächlich keine Zeit, es zu demonstrieren, aber jeder Testfall (viele Tausende) gibt immer einen topologisch sortierten kondensierten Graphen zurück.
Tags und Links algorithm graph topological-sort tarjans-algorithm