Depth-First Search (DFS): Tiefensuche von den Grundlagen bis zur Praxis

DFS folgt einem Pfad so tief wie möglich und geht bei einer Sackgasse zurück, um einen anderen Zweig zu untersuchen.

Die Implementierung erfolgt mit Rekursion oder einem expliziten Stack.

JavaScript

function dfs(graph, start) {
  const visited = new Set();
  const order = [];

  function visit(node) {
    if (visited.has(node)) return;

    visited.add(node);
    order.push(node);

    for (const next of graph[node] ?? []) {
      visit(next);
    }
  }

  visit(start);

  return order;
}

DFS vs BFS

DFS:

Stack / Rekursion
tiefenorientiert

BFS:

Queue
ebenenorientiert

BFS garantiert bei ungewichteten Graphen den kürzesten Weg. DFS ist natürlicher für Backtracking, Cycle Detection und Dependency-Strukturen.

Connected Components

Ein neuer DFS-Aufruf von jedem noch nicht besuchten Knoten entdeckt jeweils eine neue Komponente.

Cycle Detection

Bei ungerichteten Graphen muss der Parent berücksichtigt werden.

Bei gerichteten Graphen wird häufig ein Zustandssystem verwendet:

unvisited
visiting
finished

Eine Kante zu einem visiting-Knoten zeigt einen Zyklus.

Topological Sort

DFS kann Knoten nach Abschluss aller Abhängigkeiten in eine Liste einfügen. Die umgekehrte Finish-Reihenfolge ergibt eine topologische Sortierung eines DAG.

Backtracking

Viele Backtracking-Probleme sind DFS auf einem Zustandsbaum:

choose
recurse
undo

Anwendungen

• Dateisysteme
• DOM und AST
• Dependency Graphs
• Circular Dependencies
• Connected Components
• Maze und Grid
• Netzwerktopologien

Komplexität

Mit Adjazenzlisten:

Zeit: O(V + E)
Speicher: O(V)

Fazit

DFS ist nicht nur ein Traversal-Algorithmus, sondern die Grundlage vieler fortgeschrittener Graphverfahren wie SCC, Bridges, Articulation Points und Topological Sort.