Warum ist die topologische Sortierung für den längsten Pfad in der gerichteten azyklischen Grafik erforderlich?

Question

Problem: Wenn Sie einen gewichteten gerichteten azyklischen Graphen (DAG) und einen Quellknoten s in ihm angeben, finden Sie die längsten Abstände von s zu allen anderen Vertices im gegebenen Graphen.

Sie finden den Referenzgraphen: link

Warum brauchen wir topologische Sortierung? Können wir nicht einfach modifiziertes BFS vom Quellknoten verwenden? Warum kümmern wir uns so sehr um die lineare Ordnung?

Wenn dies eine Wiederholung ist, dann leiten Sie mich bitte zu relevanten Antworten um.

Dank

Answer 1

Wenn wir es nicht sortieren, wissen wir nicht benachbarten Ecke, die erste zu wählen und es kann zu einer Situation führen, wo wir Abstand von einem Scheitelpunkt v verwenden Abstände ihrer benachbarten Eckpunkten zu aktualisieren adj[v], aber danach wird die Entfernung von Vertex v aktualisiert, sodass Vertices von adj[v] auch größere Distanzen bekommen können, aber wir werden sie nicht mehr besuchen.

Beispiel basierend auf der Grafik, die Sie verwiesen haben (http://www.geeksforgeeks.org/wp-content/uploads/LongestPath.png):
Lassen Sie uns sagen, dass in diesem Schritt:

wir wählen Vertex mit Abstand 6 (statt Vertex mit Abstand 2, die wir gewählt haben würde, wenn wir hatten topologische Ordnung benutzt). Bereits verarbeitete Ecken grün sind, Vertex gerade bearbeitet wird rot:

Wir haben den Abstand des letzten Stützpunkt zu 7 aktualisiert und wir werden es nicht erhöhen, aber wenn wir Vertex mit Abstand 2 in vorherigen Schritt besucht hatte, Der Abstand dieses Eckpunkts wäre 10:

Answer 2

Wenn wir die besuchten Knoten verfolgen können, sollte es möglich sein, ein rekursives DFS und einige Memoization zu verwenden.

Start vom Startknoten. Berechnen Sie für jeden Nachbarn (Entfernung zum Nachbarn + Entfernung vom Nachbar zum Ziel). Nimm das Maximum davon, memotiere es als Maximum von diesem Knoten und gib es zurück.

Grundsätzlich, wenn Sie die maximale Entfernung von Ihren Nachbarn zum Ziel kennen, kennen Sie die maximale Entfernung von Ihnen zum Ziel. Und wenn Sie Memo machen, werden Sie keinen Knoten mehr als einmal besuchen.

Answer 3

Wenn Sie wissen, wie man es mit "modifiziertem BFS" macht, dann können Sie es so machen. Wie schlagen Sie vor, es mit "modifiziertem BFS" zu tun, BTW?

In der Zwischenzeit führt der Algorithmus, der an der Verbindung präsentiert wird, durch erste toposorting den Graph durch. So ist dieser Algorithmus konzipiert.

Nun wird die Toposort-Reihenfolge von DFS algirithm auf seiner Backtracking-Stufe erzeugt. Leider generiert DFS Toposort-Auftrag in umgekehrte Richtung. Aus diesem Grund können wir die spezifische Verarbeitung des Longest-Path-Algorithmus nicht direkt in DFS "einbetten". (Dieser Algorithmus erfordert die Verarbeitung in vorwärts Richtung.) Daher müssen wir zwei-Pass-Ansatz übernehmen: machen Sie pure DFS zuerst, um eine vollständige toposorted-Sequenz zu erstellen, und dann einen zweiten Durchgang, um den längsten Pfad zu finden.

In vielen realen Situationen sind Algorithmen, die auf Toposort basieren, wertvoll, da Knoten der DAG möglicherweise bereits in toposortierter Reihenfolge gespeichert sind. I.e. toposorting wird nur einmal in der Vorverarbeitung durchgeführt. Danach werden verschiedene toposortbasierte Algorithmen effektiv zu sehr effizienten One-Pass-Algorithmen ohne zusätzlichen Speicherbedarf (im Gegensatz zu Algorithmen wie BFS oder DFS, die zusätzlichen Speicher für ihre Stacks, Warteschlangen usw. benötigen).