Graphdurchquerungen

Tiefe zuerst und Breite zuerst sind zwei gängige Methoden zum Durchlaufen eines Diagramms.
Graph-Traversal ist der Prozess, bei dem jeder Scheitelpunkt im Diagramm genau einmal besucht wird. Es gibt zwei beliebte Methoden zum Durchlaufen eines Diagramms: Tiefendurchquerung (oder Tiefensuche) und Breite-zuerst-Durchquerung (oder Breite). -erste Suche). Beide Durchläufe führen zu einem Spanning Tree, der mithilfe einer Klasse modelliert werden kann, wie in der Abbildung unten dargestellt. Beachten Sie, dass Tree eine innere Klasse ist, die in der Klasse AbstractGraph definiert ist. AbstractGraph.Tree unterscheidet sich von der Tree-Schnittstelle, die in „Nach einem Element suchen“ definiert ist. AbstractGraph.Tree ist eine spezielle Klasse zur Beschreibung der Eltern-Kind-Beziehung der Knoten, während die Tree-Schnittstelle allgemeine Vorgänge wie Suchen, Einfügen und Löschen in einem Baum definiert. Da diese Operationen für einen Spanning Tree nicht ausgeführt werden müssen, ist AbstractGraph.Tree nicht als Untertyp von Tree.

definiert

Die Klasse Tree ist als innere Klasse in der Klasse AbstractGraph in den Zeilen 226–293 in AbstractGraph.java definiert. Der Konstruktor erstellt einen Baum mit der Wurzel, den Kanten und einer Suchreihenfolge.

Die Klasse Tree definiert sieben Methoden. Die Methode getRoot() gibt die Wurzel des Baums zurück. Sie können die Reihenfolge der gesuchten Scheitelpunkte ermitteln, indem Sie die Methode getSearchOrder() aufrufen. Sie können getParent(v) aufrufen, um das übergeordnete Element des Scheitelpunkts v in der Suche zu finden. Der Aufruf von getNumberOfVerticesFound() gibt die Anzahl der gesuchten Scheitelpunkte zurück. Die Methode getPath(index) gibt eine Liste von Scheitelpunkten vom angegebenen Scheitelpunktindex bis zur Wurzel zurück. Durch Aufrufen von printPath(v) wird ein Pfad vom Stammverzeichnis zu v angezeigt. Sie können alle Kanten im Baum mit der Methode printTree() anzeigen.

Das obige ist der detaillierte Inhalt vonGraphdurchquerungen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!