Dieser Algorithmus eignet sich hervorragend zum Durchlaufen der Knoten in einem Diagramm.
%Vor%Ich kann damit einen Zielknoten im Graphen finden. Der Arbeitsvorrat hebt die Einträge auf (oder öffnet sie), wenn der Arbeitsvorrat verarbeitet wird. Sobald ich das Ziel gefunden habe, wie kann ich den vollständigen Pfad zum Knoten zurückgeben?
Aktualisieren Ich versuche herauszufinden, wie man den Pfad zur Wurzel umkehren kann. Die Methode wird auf dem Wurzelknoten aufgerufen, danach können untergeordnete Elemente zwei Eltern haben, so dass es nicht so einfach ist, die Elterneigenschaft auf jedem Knoten aufzurufen und die Daten zurück zu transportieren.
Ziel der Methode ist es, den Pfad zu finden, nicht alle Knoten zu iterieren oder zu prüfen, ob ein Knoten existiert.
Verfolgen Sie die Vorgängerknoten. In der einfachsten Ausführung ist dies ein Wörterbuch, und in der Regel als π in pseudo-Codes bezeichnet:
%Vor% Dann können Sie diese Vorgänger durchlaufen, um den Pfad von jedem Knoten zurück zu verfolgen, sagen wir e :
Ich habe versucht, dieses Snippet zu verwenden, um die alternativen Pfade von Scheitelpunkt (Scheitelpunkte in meinem Code) zu bekommen, mit Quelle und Schicksal, aber einfach nicht funktionieren ...
%Vor%Grundsätzlich wird die Operation alle markierten Kanten erhalten (Selecionado = true) und erneut verifizieren, wenn es notwendig ist, fortzufahren ausgewählt ...
In diesem Beispiel möchte ich den kürzesten Pfad vom Vertex 'N' zum Scheitelpunkt 'Q' erhalten:
Siehe ein Vorschaubild hier:
Ist "das", das heißt, die aktuelle Instanz, die "Wurzel" des Graphen, wenn es so etwas gibt?
Ist der Graph zyklisch oder azyklisch? Ich fürchte, ich kenne nicht alle Begriffe für die Graphentheorie.
Hier ist was ich wirklich frage:
%Vor%Hier sind meine Fragen:
Wenn der Graph nie wieder zusammenkommt, wenn er sich aufteilt, keine Zyklen enthält und "dies" immer der Stamm / Start des Graphen ist, wird ein einfaches Wörterbuch den Pfad behandeln.
%Vor%Fügen Sie für jeden von Ihnen besuchten Knoten den benachbarten Knoten als Schlüssel und den Knoten als Nachbar hinzu. Dies ermöglicht es Ihnen, sobald Sie den Zielknoten gefunden haben, zurückzugehen, um den umgekehrten Pfad zu erhalten.
Mit anderen Worten, das Wörterbuch für das obige Diagramm wäre nach einem vollständigen Durchlauf:
%Vor%Um den Pfad zum E-Knoten zu finden, gehen Sie einfach zurück:
%Vor%Was dir den Pfad gibt:
%Vor%Da Sie den Pfad zum "aktuellen" Knoten nicht immer verfolgen, müssen Sie dies konstruieren, wenn Sie das Ziel gefunden haben. Wenn Ihre Knotenklasse über eine Parent-Eigenschaft verfügt, können Sie die Struktur leicht zurückverfolgen, um den vollständigen Pfad zu erstellen.
Peter ist fast richtig. Ich glaube nicht, dass Sie eine Verknüpfung zum übergeordneten Vertex in der Knotenklasse speichern können, da sie sich abhängig von dem Scheitelpunkt ändert, an dem Sie die Breite der ersten Suche starten. Sie müssen ein übergeordnetes Wörterbuch erstellen, wobei die Schlüssel Knoten und die Werte übergeordnete Knoten sein müssen. Wenn Sie jeden Scheitelpunkt (aber vor der Verarbeitung) besuchen, fügen Sie die Eltern dem Wörterbuch hinzu. Dann können Sie den übergeordneten Pfad zurück zum Wurzelknotenpunkt gehen.