How it works?

DFS führt eine besucht-Markierung für jeden Knoten und einen Stack von zu verarbeitenden Knoten.

Schritt-für-Schritt-Prozess:

1. Legen Sie den Startknoten auf den Stack (Push).
2. Nehmen Sie einen Knoten vom Stack (Pop). Wenn er bereits besucht wurde, überspringen Sie ihn. Markieren Sie ihn andernfalls als besucht und zeichnen Sie ihn in der Besuchsreihenfolge auf.
3. Legen Sie seine unbesuchten Nachbarn auf den Stack. Um sie in aufsteigender Reihenfolge zu besuchen, legen Sie sie vom größten zum kleinsten ab, damit der kleinste zuerst entnommen wird.
4. Wiederholen Sie den Vorgang, bis der Stack leer ist.

Beispiel für die Knoten 0..3 mit den Kanten [0,1, 0,2, 1,3, 2,3], beginnend bei 0:

• Besuche 0, dann den kleinsten Nachbarn 1, dann den Nachbarn 3 von 1, dann den Nachbarn 2 von 3.
• Besuchsreihenfolge: [0, 1, 3, 2].

Es werden nur Knoten besucht, die vom Startpunkt aus erreichbar sind.