Graphdurchquerungen

Tiefe zuerst und Breite zuerst sind zwei gängige Methoden zum Durchlaufen eines Diagramms.
Graph-Traversalist der Prozess, bei dem jeder Scheitelpunkt im Diagramm genau einmal besucht wird. Es gibt zwei gängige Methoden zum Durchqueren eines Diagramms:Tiefendurchquerung(oderTiefensuche) undBreitendurchquerung(oderBreitensuche). Beide Durchläufe führen zu einem Spanning Tree, der mithilfe einer Klasse modelliert werden kann, wie in der Abbildung unten dargestellt. Beachten Sie, dassTreeeine innere Klasse ist, die in der KlasseAbstractGraphdefiniert ist.AbstractGraph.Treeunterscheidet sich von der in „Suchen nach einem Element“ definiertenTree-Schnittstelle.AbstractGraph.Treeist eine spezielle Klasse zur Beschreibung der Eltern-Kind-Beziehung der Knoten, während dieTree-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, istAbstractGraph.Treenicht als Untertyp vonTree.

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

Die KlasseTreedefiniert sieben Methoden. Die MethodegetRoot()gibt die Wurzel des Baums zurück. Sie können die Reihenfolge der gesuchten Scheitelpunkte ermitteln, indem Sie die MethodegetSearchOrder()aufrufen. Sie könnengetParent(v)aufrufen, um das übergeordnete Element des Scheitelpunktsvin der Suche zu finden. Der Aufruf vongetNumberOfVerticesFound()gibt die Anzahl der gesuchten Scheitelpunkte zurück. Die MethodegetPath(index)gibt eine Liste von Scheitelpunkten vom angegebenen Scheitelpunktindex bis zur Wurzel zurück. Durch Aufrufen vonprintPath(v)wird ein Pfad vom Stammverzeichnis zuvangezeigt. Sie können alle Kanten im Baum mit der MethodeprintTree()anzeigen.

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