tarjans-algorithm, Seitenzahl 1

___ answer37575421 ___

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.

___ answer42701518 ___

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.

___ tag123graph ___ Graph bezieht sich auf eine Grafik (z. B. ein Diagramm oder ein Diagramm), die die Beziehung zwischen zwei oder mehr Variablen anzeigt. Verwenden Sie für die diskrete mathematische Struktur, die aus Vertices und Kanten besteht, das Diagramm-Theorie-Tag. ___ qstnhdr ___ Gibt Tarjans SCC-Algorithmus eine topologische Sortierung des SCC? ___ tag123algorithm ___ Ein Algorithmus ist eine Folge wohldefinierter Schritte, die eine abstrakte Lösung für ein Problem definieren. Verwenden Sie dieses Tag, wenn sich Ihr Problem auf den Algorithmusentwurf bezieht. ___ answer43598758 ___

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%

___ qstntxt ___

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?

___ tag123topologicalsort ___ Eine topologische Art eines gerichteten Graphen erzeugt eine lineare Ordnung seiner Ecken, so dass für jede Kante uv u vor v in der Ordnung kommt. ___ tag123tarjansalgorithm___ Tarjans Algorithmus ist ein linearer Algorithmus zum Auffinden aller stark verbundenen Komponenten eines gerichteten Graphen. ___