Datenstruktur - Tiefe erste Durchquerung
Der DFS-Algorithmus (Depth First Search) durchläuft einen Graphen in einer Tiefenbewegung und verwendet einen Stapel, um sich daran zu erinnern, den nächsten Scheitelpunkt zum Starten einer Suche zu erhalten, wenn in einer Iteration eine Sackgasse auftritt.
Wie im obigen Beispiel durchläuft der DFS-Algorithmus zuerst von S nach A nach D nach G nach E nach B, dann nach F und zuletzt nach C. Er verwendet die folgenden Regeln.
Rule 1- Besuchen Sie den angrenzenden nicht besuchten Scheitelpunkt. Markieren Sie es als besucht. Zeigen Sie es an. Schieben Sie es in einen Stapel.
Rule 2- Wenn kein benachbarter Scheitelpunkt gefunden wird, öffnen Sie einen Scheitelpunkt aus dem Stapel. (Es werden alle Scheitelpunkte aus dem Stapel angezeigt, die keine benachbarten Scheitelpunkte haben.)
Rule 3 - Wiederholen Sie Regel 1 und Regel 2, bis der Stapel leer ist.
| Schritt | Durchquerung | Beschreibung |
|---|---|---|
| 1 |
|
Initialisieren Sie den Stapel. |
| 2 |
|
Kennzeichen Swie besucht und auf den Stapel legen. Erkunden Sie alle nicht besuchten benachbarten Knoten vonS. Wir haben drei Knoten und können jeden von ihnen auswählen. In diesem Beispiel nehmen wir den Knoten in alphabetischer Reihenfolge. |
| 3 |
|
Kennzeichen Awie besucht und auf den Stapel legen. Untersuchen Sie alle nicht besuchten benachbarten Knoten von A. BeideS und D sind neben A Wir sind jedoch nur für nicht besuchte Knoten besorgt. |
| 4 |
|
Besuch Dund als besucht markieren und auf den Stapel legen. Hier haben wirB und C Knoten, die benachbart sind Dund beide sind nicht besucht. Wir werden jedoch wieder in alphabetischer Reihenfolge wählen. |
| 5 |
|
Wir wählen B, als besucht markieren und auf den Stapel legen. HierBhat keinen nicht besuchten Nachbarknoten. Also knallen wirB vom Stapel. |
| 6 |
|
Wir überprüfen die Stapeloberseite auf Rückkehr zum vorherigen Knoten und prüfen, ob nicht besuchte Knoten vorhanden sind. Hier finden wirD auf dem Stapel sein. |
| 7 |
|
Nur nicht besuchte benachbarte Knoten sind von D ist Cjetzt. Also besuchen wirC, markieren Sie es als besucht und legen Sie es auf den Stapel. |
Wie Chat keinen nicht besuchten Nachbarknoten, daher knallen wir den Stapel weiter, bis wir einen Knoten finden, der einen nicht besuchten Nachbarknoten hat. In diesem Fall gibt es keine und wir knallen weiter, bis der Stapel leer ist.
Klicken Sie hier , um mehr über die Implementierung dieses Algorithmus in der Programmiersprache C zu erfahren .