Suche in Graphen: BFS und DFS

1736 zeigte Leonhard Euler, dass kein Spaziergang jede der sieben Brücken von Königsberg genau einmal überquert, und mit dieser Antwort begann die Graphentheorie.

Punkte und Linien

Ein Graph ist eine Menge von Punkten, genannt Knoten (Ecken), die durch Linien verbunden sind, genannt Kanten. Die Idee ist schlicht und passt auf eine riesige Bandbreite von Dingen: Städte, verbunden durch Straßen, Webseiten, verbunden durch Links, Menschen, verbunden durch Freundschaften, Felder eines Labyrinths, verbunden, wo keine Wand ist. Ist ein Problem erst einmal als Graph gezeichnet, beantwortet dieselbe Handvoll Algorithmen Fragen wie „Komme ich von hier nach dort?“ und „Was ist der kürzeste Weg?“

Einen Graphen im Code speichern

Ein üblicher Weg, einen Graphen zu speichern, ist eine Adjazenzliste: zu jedem Knoten eine Liste seiner Nachbarn. Die Unterlagen des MIT-Kurses 6.006 verwenden genau das, ein Array oder Wörterbuch Adj, in dem Adj[u] die mit u verbundenen Knoten auflistet. Für den Graphen oben sieht das so aus:

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

Breitensuche: Ring für Ring

Die Breitensuche (BFS, breadth-first search) erkundet einen Graphen in Ringen um den Start. Zuerst den Start selbst, Abstand 0. Dann alle seine Nachbarn, Abstand 1. Dann jeden neuen Knoten neben diesen, Abstand 2, und so weiter. Dafür hält sie eine Warteschlange (Queue), eine Reihe, in der das Erste, was hineinkommt, auch zuerst herauskommt. Nimm den Knoten vorn in der Warteschlange, besuch ihn und häng seine noch nicht gesehenen Nachbarn hinten an. Von A aus besucht die Breitensuche im Beispiel A, dann B und C, dann D und E, dann F. Weil sie sich Ring für Ring nach außen bewegt, hat sie beim ersten Erreichen eines Knotens einen Weg mit den wenigsten Kanten gefunden. F liegt 3 Kanten von A entfernt, zum Beispiel über A, B, D, F.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // zuerst hinein, zuerst heraus
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

Tiefensuche: so weit wie möglich, dann zurück

Die Tiefensuche (DFS, depth-first search) verhält sich wie jemand im Labyrinth, der eine Hand an der Wand behält. Sie folgt einem Weg, so tief es geht. Kommt sie in eine Sackgasse oder an eine Stelle, die sie schon kennt, geht sie zur letzten Abzweigung zurück und probiert die nächste Möglichkeit. Sie verwendet statt einer Warteschlange einen Stapel, last in, first out, und lässt sich ganz natürlich mit Rekursion schreiben, wobei sich der Aufrufstapel alles merkt. Von A aus besucht eine rekursive Tiefensuche A, B, D, C, E, F. Die Tiefensuche erreicht jeden Knoten, den die Breitensuche erreicht, aber ihr Weg ist nicht unbedingt der kürzeste.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // A B D C E F
}

Welche nimmt man?

Im ersten Labyrinth des Labors besucht die Breitensuche 105 Felder und findet einen Weg mit 22 Zügen, den kürzesten möglichen. Die Tiefensuche taucht zufällig in Richtung Ziel ab und besucht nur 31 Felder, aber ihr Weg braucht 28 Züge. Keine ist immer billiger. Beide behandeln jeden Knoten und jede Kante eine feste Zahl von Malen, also laufen beide in O(V + E) Zeit bei V Knoten und E Kanten. Nimm die Breitensuche, wenn du die wenigsten Schritte brauchst: die wenigsten Züge in einem Rätsel, die wenigsten Verbindungen zwischen zwei Menschen. Nimm die Tiefensuche, wenn du alles erkunden oder Entscheidungen bis zum Ende verfolgen musst: prüfen, ob alle Räume eines Labyrinths verbunden sind, oder die Züge eines Rätsels eine Linie nach der anderen ausprobieren und zurückgehen, wenn es nicht weitergeht. Haben Kanten verschiedene Längen, wie Straßen, reicht keine von beiden allein. Verfahren wie der Dijkstra-Algorithmus erweitern die Idee der Breitensuche um Entfernungen.