Breitensuche und Tiefensuche (BFS und DFS)

Kurz: Breitensuche und Tiefensuche sind zwei Wege, einen Graphen oder Baum vollständig zu durchlaufen. BFS geht Ebene für Ebene, DFS so tief wie möglich, bevor es zurückgeht.

Genauer: BFS nutzt eine Warteschlange (Queue-Datenstruktur) und findet in einem Graphen ohne Gewichte den kürzesten Weg (gemessen in Kanten). DFS nutzt einen Stapel (Stack-Datenstruktur) oder Rekursion (Rekursion) und eignet sich für Labyrinthe, Zyklensuche und topologische Sortierung. Beide brauchen O(V + E) Zeit.

Im Detail

• BFS: Start in die Warteschlange, immer den vordersten Knoten nehmen, seine unbesuchten Nachbarn hinten anhängen.
• DFS: Nächsten unbesuchten Nachbarn besuchen, bei Sackgasse zurück (Backtracking).
• Besucht-Markierung: Verhindert Endlosschleifen bei Zyklen.
• Beispiele: Kürzester Weg in einem Labyrinth (BFS), Zusammenhangskomponenten (DFS), Netzwerke, soziale Kontakte („Grad der Trennung”).
• Speicher: BFS braucht viel Platz bei breiten Graphen, DFS bei tiefen.

Siehe auch: Graph-Datenstruktur, Dijkstra-Algorithmus, Big-O-Notation