Motivation
Lektion 2 von 9 im Kurs Tiefensuche - Graph-Algorithmen von Coddy.
DFS exploriert einen Graphen, indem sie einem Pfad folgt, so weit es geht, und dann zum letzten Knoten mit einem nicht explorierten Nachbarn zurückkehrt.
Warum DFS lernen?
- Grundlegend: Sie bildet die Basis für Zyklenerkennung, topologisches Sortieren, Zusammenhangskomponenten und viele andere Algorithmen.
- Einfach und effizient: Sie läuft in O(V + E) Zeit unter Verwendung eines Stacks (oder Rekursion) und einer Markierung für besuchte Knoten.
- Vielseitig: Dieselbe Traversierung beantwortet Fragen wie „Sind diese zwei Knoten verbunden?“ und „Aus wie vielen separaten Teilen besteht der Graph?“
Um die Ergebnisse vorhersehbar zu halten, besuchen wir die Nachbarn eines Knotens immer in aufsteigender Reihenfolge.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
