Breadth-First Search (BFS): Graphen Ebene für Ebene durchsuchen

BFS untersucht zuerst alle Knoten in Abstand 1, dann Abstand 2 usw. Dafür verwendet der Algorithmus eine FIFO-Queue.

Die wichtigste Eigenschaft: In ungewichteten oder gleich gewichteten Graphen liefert die erste Entdeckung eines Knotens dessen minimale Kantendistanz.

JavaScript

function bfs(graph, start) {
  const queue = [start];
  let head = 0;
  const visited = new Set([start]);
  const order = [];

  while (head < queue.length) {
    const current = queue[head++];

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;
      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

Knoten sollten bereits beim Enqueue als besucht markiert werden.

Shortest Path

Mit distance wird die minimale Anzahl von Kanten gespeichert. Mit parent kann anschließend der konkrete Pfad rekonstruiert werden.

BFS vs DFS

BFS arbeitet mit einer Queue und Ebenen. DFS nutzt Stack oder Rekursion und geht zunächst tief in einen Zweig.

Grid und Maze

Zellen sind Knoten, erlaubte Bewegungen sind Kanten. Bei gleichen Bewegungskosten findet BFS die minimale Anzahl von Schritten.

Multi-Source BFS

Mehrere Startpunkte werden gleichzeitig mit Distanz 0 in die Queue gelegt.

Bidirectional BFS

Bei bekanntem Start und Ziel kann eine Suche von beiden Seiten den Suchraum stark verkleinern.

0-1 BFS

Bei Kantengewichten nur 0 oder 1 eignet sich eine Deque-basierte Variante.

Anwendungen

• soziale Netzwerke
• Maze und Grid
• Web Crawling
• Connected Components
• Bipartite Check
• Minimum-Move-Probleme

Komplexität

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

Fazit

BFS ist die Standardwahl für ungewichtete Shortest Paths, Level-Order Traversal und viele Minimum-Move-Probleme.