Tiefendurchquerung und Breitendurchquerung

Tiefendurchquerung

Angenommen, der Anfangszustand eines gegebenen Graphen G ist, dass nicht alle Eckpunkte besucht wurden. Wählen Sie einen beliebigen Scheitelpunkt v in G als anfänglichen Startpunkt (Quellpunkt), dann kann die Tiefendurchquerung wie folgt definiert werden: Besuchen Sie zuerst den Startpunkt v und markieren Sie ihn als besucht. Beginnen Sie dann bei v, um jeden benachbarten Punkt zu durchsuchen v. w. (Empfohlenes Lernen: Web-Frontend-Video-Tutorial)

Wenn w noch nicht besucht wurde, verwenden Sie w als neuen Ausgangspunkt, um die Tiefendurchquerung fortzusetzen, bis alle Pfade im Diagramm vorhanden sind Pfade zum Quellpunkt haben v Bis alle verbundenen Scheitelpunkte (auch vom Quellpunkt aus erreichbare Scheitelpunkte genannt) besucht wurden.

Wenn es zu diesem Zeitpunkt noch nicht besuchte Scheitelpunkte im Diagramm gibt, wählen Sie einen anderen nicht besuchten Scheitelpunkt als neuen Quellpunkt aus und wiederholen Sie den obigen Vorgang, bis alle Scheitelpunkte im Diagramm besucht wurden.

Die Tiefendurchquerung eines Diagramms ähnelt der Vorbestellungsdurchquerung eines Baums. Das Merkmal der verwendeten Suchmethode besteht darin, so weit wie möglich zuerst in Tiefenrichtung zu suchen. Diese Suchmethode wird als Tiefensuche bezeichnet. Dementsprechend wird das Durchlaufen des Diagramms mit dieser Methode natürlich als Tiefendurchquerung des Diagramms bezeichnet.

Um es ganz klar auszudrücken: Die Tiefendurchquerung ist ein Algorithmus, der nicht an die Wand stößt. Nach Abschluss eines Pfads kehrt er zum verzweigten Knoten zurück und setzt die Durchquerung fort.

Wie in der Abbildung gezeigt:

Breitenorientierte Durchquerung

Von Irgendwo in der Abbildung: Beginnen Sie mit dem Scheitelpunkt V0 und besuchen Sie diesen Scheitelpunkt. ...,Woche, jeden dieser nicht besuchten benachbarten Punkte besuchen

Wiederholen Sie Schritt 2, bis alle Eckpunkte besucht sind.

Dies ist ein Schicht-für-Schicht-Algorithmus, ähnlich dem Durchlaufen eines Baums in Schichtreihenfolge.

Während der Breitensuche wird er vom Startpunkt aus in einer „Schicht für Schicht“-Erweiterungsmethode durchlaufen. Während der Erweiterung wird jedes Mal, wenn ein Punkt gefunden wird, der Warteschlange hinzugefügt, bis er vollständig ist Der Graph wurde durchlaufen.

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