Wirklich brauchen nur ein wenig Anleitung: Topologische Sortierung nach Arcs Definition (aus meiner Frage) - ist eine Möglichkeit, alle Bögen in gerichteten Graphen zu bestellen, so dass alle Bögen, die in den Scheitelpunkt einfügen müssen, vor dem kommen aus diesem Eckpunkt heraus.Topologische Sortierung nach Bögen
Keine Notwendigkeit, in der topologischen Sortierung etwas zu ändern, Sie können es einfach verwenden und nachbearbeiten.
hohe Pseudocode:
arrlv in arr [geordneten Iteration] sein : (v,u) in E: (v,u) to llDer Vorteil dieser Methode ist, dass Sie topologische Sortierung als Blackbox verwenden können, ohne Modifizierung es und einfach nachbearbeiten das gewünschte Ergebnis zu erhalten. für jede Kante
Da (v,u) - u nach v in topologische Sortierung angezeigt wird, wenn sie gedruckt wird, wird es über v gemacht, und somit (v,u) gedruckt wird, bevor Sie jedes Vertex drucken:
Korrektheits [Skizze des Beweises] befestigt an u.
Komplexität: O(|V|+|E|) topologische Sortierung, O(|V|+|E|) für die Nachbearbeitung [Iterieren allen Ecken und alle Kanten].
"Traditionelle" topologische Sortierung ist die Sortierung von Vertices, während diese Sortierung von Bögen ist. Ansonsten ist das Prinzip das gleiche ...
Ich weiß, aber wenn ich in topologischen Sortierung Algorithmus sehe ich nicht unterschreiben, wie es für Bögen geändert werden kann ... Ich will nicht, dass Sie es für mich lösen, aber ich brauche eine Anleitung bitte – Nusha
Gehen Sie zum Wiki Seite, die Sie bestanden haben, Opcode-Abschnitt. Lassen Sie "n in L einfügen" und beim Schritt "Kante e aus der Grafik entfernen" fügen Sie auch "Kante e in L" ein. Auf diese Weise erinnern Sie sich an Bögen anstelle von Scheitelpunkten. – tchap
Yeah, big-O ist das gleiche, aber du musst doppelt so viel Arbeit machen ... – tchap
@OndrejKupka: In der Tat wird die Konstante höher sein als die topologische Sortierung modifizieren [obwohl ich glaube nicht, dass ich aufgrund der Cache-Leistung doppelt bin], aber zum Vorteil der ** topologischen Sortierung **. [was sehr wichtiger Aspekt ist!]. In realen Anwendungen, * wenn Sie herausfinden, dass dieser Teil ein Hotspot * ist, werden Sie ihn wahrscheinlich neu schreiben wollen, einverstanden. – amit
Ja, es ist nicht wirklich praktisch, so viel Code für nichts zu kopieren. – tchap