BFS: die wenigsten Haltestellen

Code in:JavaC#PythonJavaScript

Kurz gesagt: BFS (Breitensuche) erkundet einen Graphen Schicht für Schicht mit einer Warteschlange und findet den Weg mit den wenigsten Kanten in O(V + E).

Problem

Sechs Straßen statt vier

Der Disponent des Kurierdienstes will eine Route vom Lager zum Krankenhaus mit den wenigsten Straßen. In dieser Stadt bedeutet jede Straße eine Ampel, eine Abbiegung und einen Halt, darum zählt die Zahl der Straßen mehr als die Meter.

Ein Kollege hat eine Suche geschrieben, die die erste freie Straße nimmt und weitermacht, bis sie ankommt. Bleibt sie stecken, geht sie zurück und probiert die nächste:

function anyRoute(graph, at, target, seen) {
  if (at === target) return [at];
  seen.add(at);
  for (const next of graph.get(at)) {
    if (seen.has(next)) continue;
    const rest = anyRoute(graph, next, target, seen);
    if (rest !== null) return [at, ...rest];
  }
  return null;
}

const route = anyRoute(graph, "Lager", "Krankenhaus", new Set());
console.log(`${route.join(" → ")}: ${route.length - 1} Straßen`);

Ausgabe

Lager → Bahnhof → Platz → Markt → Park → Stadion → Krankenhaus: 6 Straßen

Es gibt eine Route, aber sie hat 6 Straßen. Sieh dir die Karte aus der vorigen Lektion an: Lager → Bahnhof → Platz → Kino → Krankenhaus sind 4. Die Suche hat keinen Fehler gemacht: Sie hat nie nach der kürzesten gefragt, sie hat die erste genommen, die sie fand.

Die Idee

Eine Welle vom Lager

Stell dir eine Welle vor, die das Lager verlässt. Zuerst erreicht sie alle Haltestellen, die eine Straße entfernt sind. Dann von ihnen aus alle neuen Haltestellen, die zwei Straßen entfernt sind. Dann drei. Eine Haltestelle, die die Welle erreicht hat, ist vergeben: Die nächsten Wellen fassen sie nicht an.

Eine Haltestelle bekommt ihre Entfernung also in dem Moment, in dem die Welle sie zum ersten Mal berührt, und das ist die kleinste mögliche.

Die Reihenfolge „erst die näheren“ hält eine Warteschlange: Gefundene Haltestellen reihen sich hinten ein, und die, die gerade bearbeitet wird, geht vorn weg. Das ist BFS (Breitensuche, englisch breadth-first search).

• dist speichert die Entfernung jeder gefundenen Haltestelle. Es ist zugleich die Menge der gesehenen Haltestellen: Eine Haltestelle mit einem dist kommt nicht ein zweites Mal in die Warteschlange.
• prev speichert, von wo jede Haltestelle gefunden wurde. Damit wird später die Route selbst aufgebaut.

Sieh es dir an

Schicht für Schicht

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const stop = queue[head];
    for (const next of graph.get(stop)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(stop) + 1);
      prev.set(next, stop);
      queue.push(next);
    }
  }
  return { dist, prev };
}

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const stop = queue[head];
    for (const next of graph.get(stop)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(stop) + 1);
      prev.set(next, stop);
      queue.push(next);
    }
  }
  return { dist, prev };
}

function pathTo(prev, target) {
  const path = [];
  let at = target;
  while (at !== undefined) {
    path.push(at);
    at = prev.get(at);
  }
  return path.reverse();
}

Schritt für Schritt, in Worten

1. Wir starten bei Lager: dist = 0, und es ist die einzige Haltestelle in der Warteschlange.
2. Lager verlässt die Warteschlange. Die Nachbarn Bahnhof und Markt sind neu: dist = 1, prev = Lager, und sie reihen sich hinten ein.
3. Bahnhof: Lager hat schon ein dist und wird übersprungen. Platz bekommt dist = 2.
4. Markt sieht auch Platz, aber Platz ist schon mit dist = 2 in der Warteschlange. Jede Haltestelle kommt nur einmal hinein. Park: dist = 2.
5. Schicht 2 verlässt die Warteschlange und öffnet Schicht 3: Kino hinter der Brücke und Stadion. In der Warteschlange stehen immer höchstens zwei Schichten, die nähere vorn.
6. Kino findet Krankenhaus: dist = 4. Erreicht auch Stadion sie, hat Krankenhaus schon ein dist: Die erste Ankunft ist die kürzeste.
7. Um Krankenhaus gibt es nichts Neues. Die Warteschlange ist leer: Jede Haltestelle hat ihre Entfernung vom Lager.
8. pathTo geht entlang prev zurück: Krankenhaus ← Kino ← Platz ← Bahnhof ← Lager. Umgedreht ist das die Route: 4 Straßen.

Das Programm lässt BFS vom Lager laufen und gibt die Entfernung zu jeder Haltestelle und die Route zum Krankenhaus aus:

const { dist, prev } = bfs(graph, "Lager");
for (const stop of stops) {
  console.log(`${stop}: ${dist.get(stop)}`);
}
const path = pathTo(prev, "Krankenhaus");
console.log(`${path.join(" → ")}: ${path.length - 1} Straßen`);

Ausgabe

Lager: 0
Bahnhof: 1
Markt: 1
Platz: 2
Park: 2
Kino: 3
Krankenhaus: 4
Stadion: 3
Lager → Bahnhof → Platz → Kino → Krankenhaus: 4 Straßen

Das Array ist eine Warteschlange mit einem Index head: push legt hinten ab, und head zeigt, welche vorn steht. Am Anfang des Arrays wird nichts entfernt (warum, steht unten unter „Genauer“). Wie die Warteschlange innen funktioniert, steht in der Lektion Stapel und Warteschlange.

Probier es aus

Bring die Zeilen in die richtige Reihenfolge

Das ist das Herz von BFS: ein Durchlauf der Schleife. Bring die Zeilen in die richtige Reihenfolge:

1. const stop = queue[head];↑↓
2. }↑↓
3. if (dist.has(next)) continue;↑↓
4. prev.set(next, stop);↑↓
5. dist.set(next, dist.get(stop) + 1);↑↓
6. for (const next of graph.get(stop)) {↑↓
7. queue.push(next);↑↓

Prüfen

Probier es aus

Sag die Ausgabe voraus

Dasselbe BFS, aber es startet beim Kino. Was gibt das Programm für Lager, Stadion und Park aus?

const { dist } = bfs(graph, "Kino");
const ask = ["Lager", "Stadion", "Park"];
console.log(ask.map((s) => dist.get(s)).join(" "));

Antwort

4 2 3

3 3 4

3 2 3

Prüfen

Die Idee

Die Route rückwärts

dist sagt, wie viele Straßen es sind, aber nicht, welche. Die Route steckt in prev: Das Krankenhaus wurde vom Kino aus gefunden, das Kino vom Platz, der Platz vom Bahnhof, der Bahnhof vom Lager. Das Lager hat kein prev, weil dort alles begann.

Darum wird die Route von hinten gelesen: vom Ziel entlang prev bis zum Start und am Ende umgedreht.

function pathTo(prev, target) {
  const path = [];
  let at = target;
  while (at !== undefined) {
    path.push(at);
    at = prev.get(at);
  }
  return path.reverse();
}

let at = target;
while (at !== undefined) {
  path.push(at);
  at = ;
}

Prüfen

Genauer, für Neugierige

Die Wege in prev bilden einen Baum: Jede Haltestelle zeigt auf genau eine andere, die, von der aus sie gefunden wurde, und die Wurzel ist das Lager. Das heißt BFS-Baum. Jeder Ast von der Wurzel zu einer Haltestelle ist die kürzeste Route dorthin. Darum liefert ein BFS vom Lager aus die kürzesten Routen zu allen Haltestellen auf einmal, nicht nur zum Krankenhaus.

Wurde eine Haltestelle nie gefunden (es gibt keine Route), hat sie kein dist. Prüfe das, bevor du pathTo aufrufst: Sonst bekommst du eine „Route“ aus einer Haltestelle, dem Ziel selbst.

Die Idee

Warum die erste Ankunft die kürzeste ist

Die Warteschlange enthält höchstens zwei Schichten: d und d + 1, die nähere vorn. Eine Haltestelle, die d + 1 Straßen entfernt ist, wird von einer gefunden, die d Straßen entfernt ist, und Haltestellen mit d + 2 kommen erst, wenn die mit d + 1 anfangen zu gehen. Eine Haltestelle bekommt ihr dist also von der kürzesten Route, und jede spätere Route zu ihr ist mindestens genauso lang und wird übersprungen.

Wichtig ist auch, wann eine Haltestelle als gesehen markiert wird: wenn sie in die Warteschlange kommt, nicht wenn sie sie verlässt. Sonst käme der Platz, den man sowohl vom Bahnhof als auch vom Markt aus sieht, zweimal hinein.

Genauer, für Neugierige

Der Beweis in einem Satz: durch Induktion über d verlassen alle Haltestellen mit Entfernung d die Warteschlange vor allen mit Entfernung d + 1, und jede bekommt dist = d. Das gilt nur, wenn jede Kante 1 kostet. Haben die Straßen verschiedene Längen, heißt weniger Straßen nicht weniger Meter. Dann wird die Warteschlange durch eine Prioritätswarteschlange nach der zurückgelegten Strecke ersetzt, und das ist Dijkstra (die Dijkstra-Lektion in diesem Modul).

Die Idee

Was es kostet

Jede Haltestelle kommt höchstens einmal in die Warteschlange und verlässt sie einmal. Beim Verlassen sieht sie sich ihre Straßen an. Eine Straße in beide Richtungen wird von beiden Enden aus gesehen. Insgesamt: V Abgänge und 2E Blicke, O(V + E).

Das gilt für eine Adjazenzliste. Bei einer Matrix ist „wer sind die Nachbarn“ die ganze Zeile, und BFS macht V Blicke pro Haltestelle: O(V²). Lass beide auf einer Stadt mit n Kreuzungen im Raster laufen:

• BFS mit einer Adjazenzliste O(n)
• BFS mit einer Matrix O(n²)

Algorithmus	n = 10	n = 1.000	n = 5.000	n = 100.000
BFS mit einer Adjazenzliste	36	4.872	24.716	498.734
BFS mit einer Matrix	110	1.001.000	25.005.000	≈ 10.002.000.000

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const stop = queue[head];
    for (const next of graph.get(stop)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(stop) + 1);
      prev.set(next, stop);
      queue.push(next);
    }
  }
  return { dist, prev };
}

Gezählt wird jede Haltestelle, die die Warteschlange verlässt, und jeder Blick auf einen Nachbarn. Bei 1000 Kreuzungen macht die Liste 4872 Operationen und die Matrix 1.001.000. Bei 100.000 Kreuzungen macht die Liste 498.734, etwa 5 pro Kreuzung: ein Abgang und bis zu 4 Straßen. Die Matrix liegt bei 5000 schon bei 25.005.000.

Probier es aus

Finde den Fehler

Ein Kollege hat entschieden, dass die Entfernung einer neuen Haltestelle „die nächste Zahl“ ist. Das Programm gibt aus:

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const stop = queue[head];
    for (const next of graph.get(stop)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.size);
      prev.set(next, stop);
      queue.push(next);
    }
  }
  return { dist, prev };
}

Ausgabe

Lager: 0
Bahnhof: 1
Markt: 2
Platz: 3
Park: 4
Kino: 5
Krankenhaus: 7
Stadion: 6
Lager → Bahnhof → Platz → Kino → Krankenhaus: 4 Straßen

Die Route stimmt, 4 Straßen, und doch kommt das Krankenhaus mit 7 heraus. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1function bfs(graph, start) {2 const dist = new Map([[start, 0]]);3 const prev = new Map();4 const queue = [start];5 for (let head = 0; head < queue.length; head++) {6 const stop = queue[head];7 for (const next of graph.get(stop)) {8 if (dist.has(next)) continue;9 dist.set(next, dist.size);10 prev.set(next, stop);11 queue.push(next);12 }13 }14 return { dist, prev };15}

Prüfen

Genauer

Die Warteschlange in jeder Sprache

JavaScript hat keine eingebaute Warteschlange. queue.shift() entfernt das erste Element und verschiebt laut Spezifikation alle anderen: O(n) pro Entnehmen. Das Array mit einem Index head entfernt nichts, es verschiebt nur den Index: O(1). Der Preis ist, dass das Array alle vergangenen Haltestellen behält, bis BFS endet, aber es sind V, genauso viele wie in dist.

Übung

Die Schichten der Stadt

Löse die Aufgabe in deinem Editor.

Schichten und Brücken. Gib mit BFS vom Lager aus die Haltestellen nach Schichten aus (die Haltestellen jeder Schicht in der Reihenfolge von stops) und die am weitesten entfernte Haltestelle. Dann sperre beide Brücken: Entferne sie aus der Adjazenzliste, lass BFS noch einmal laufen und gib aus, welche Haltestellen nicht mehr erreichbar sind.

const bridges = [
  ["Markt", "Park"], ["Platz", "Kino"],
];

Ausgabe

Schicht 0: Lager
Schicht 1: Bahnhof, Markt
Schicht 2: Platz, Park
Schicht 3: Kino, Stadion
Schicht 4: Krankenhaus
Am weitesten: Krankenhaus (4 Straßen)
Ohne die Brücken nicht erreichbar: Park, Kino, Krankenhaus, Stadion

Weitere Aufgaben

• Die nächste Apotheke. Einige Haltestellen haben eine Apotheke. Lass ein BFS laufen, das von allen Apotheken gleichzeitig startet (alle stehen mit dist 0 in der Warteschlange), und gib für jede Haltestelle aus, wie viele Straßen die nächste entfernt ist.
• Ein Labyrinth aus Regalen. Das Lager ist ein Raster aus Regalen (#) und Gängen (.). Finde die wenigsten Schritte vom Eingang zum Ausgang, wobei die Nachbarn einer Zelle oben, unten, links und rechts sind.
• Alle kürzesten. Zähle, wie viele verschiedene kürzeste Routen es vom Lager zu jeder Haltestelle gibt.

Test

Teste dich

1. Warum ist die erste Route, auf der BFS eine Haltestelle erreicht, die kürzeste in Straßen?

Die Warteschlange bearbeitet alle Haltestellen, die d Straßen entfernt sind, bevor sie zu denen kommt, die d + 1 entfernt sindWeil BFS alle Routen probiert und die kürzeste behältWeil die Nachbarn in der Liste nach Entfernung sortiert sind

2. Ein Kollege hat die Warteschlange durch einen Stapel ersetzt: Er nimmt die zuletzt hinzugefügte Haltestelle. Was passiert?

Das Programm läuft endlosNichts: Die Reihenfolge ist egalDer Durchlauf geht nicht mehr schichtweise, und dist kann größer ausfallen als der kürzeste Weg

3. Die Straßen haben Längen in Metern. Gibt BFS die kürzeste Route in Metern?

Nein: BFS zählt Straßen, jede Straße ist ein Schritt, egal wie lang sie istJa, wenn die Adjazenzliste auch die Meter speichertJa, immer

4. Wie viel Arbeit macht BFS in einer Stadt mit V Kreuzungen und E Straßen, gespeichert als Adjazenzliste?

O(V²)O(V · E)O(V + E): Jede Haltestelle verlässt die Warteschlange einmal, jede Straße wird zweimal angesehen

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Big-O: wie die Arbeit wächst · Speicherkomplexität · Stapel und Warteschlange · Graph: Adjazenzliste und Matrix
• Geht weiter in: DFS: Inseln und Zyklen · Topologische Sortierung · Dijkstra · Navigation in der Stadt
• Aufgaben zum Thema: Graphen