Der Netzplan als Graph
Ein Graph besteht aus Knoten und Kanten, und die Breitensuche (englisch breadth-first search, kurz BFS) findet darin den Weg mit den wenigsten Schritten. So rechnet eine App aus, mit wie wenigen Haltestellen du von A nach B kommst.
Der Netzplan einer S-Bahn ist ein Graph. Auch ein soziales Netzwerk ist einer: Die Knoten sind Menschen, die Kanten sind Freundschaften.
Am Ende dieser Lektion
Notiz
Ich kann mit der Breitensuche einen kürzesten Weg in einem Graphen finden.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Graph | Knoten, die durch Kanten verbunden sind |
| Knoten | ein Punkt im Graphen, etwa eine Haltestelle |
| Kante | eine Verbindung zwischen zwei Knoten |
| Nachbar | ein Knoten, der über eine Kante verbunden ist |
| Breitensuche | erst alle Nachbarn besuchen, dann deren Nachbarn |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Graph hat Knoten und Kanten
Ein Graph hat Knoten und Kanten. In einem S-Bahn-Netz ist jede Haltestelle ein Knoten und jede Strecke dazwischen eine Kante.
In Python speicherst du das als Wörterbuch. Der Schlüssel ist ein Knoten. Der Wert ist die Liste seiner Nachbarn.
Dasselbe Netz als Liste der Nachbarn
| Haltestelle | Nachbarn |
|---|---|
| Hafen | Markt, Park |
| Markt | Hafen, Schule, Bahnhof |
| Park | Hafen, Bahnhof |
| Schule | Markt, Stadion |
| Bahnhof | Markt, Park, Stadion |
| Stadion | Schule, Bahnhof |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Breitensuche arbeitet mit einer Warteschlange
Die Breitensuche startet am Anfangsknoten. Sie besucht zuerst alle Nachbarn, dann die Nachbarn der Nachbarn, Ring um Ring. Eine Warteschlange merkt sich, welcher Knoten als Nächstes dran ist.
Jeder Knoten wird nur einmal besucht. Darum merkt sich die Suche, wo sie schon war.
Bevor du anfängst
Notiz
Drück oben in der Leiste auf Lab starten und warte, bis JupyterLab läuft. Die Schaltflächen Ausführen tippen ihren Befehl in das Terminal neben dem Lab. Jeder startet Python im Container jupyter.
Das Netz im Lab durchsuchen
Der erste Befehl schreibt das Netz und die Breitensuche in die Datei netz.py. Er gibt nichts aus. Das Programm zeigt die Nachbarn von Markt und dann den Abstand jeder Haltestelle zum Hafen. Der zweite Befehl startet es.
Das Netz in netz.py schreiben
docker exec jupyter sh -c "printf 'netz = {\"Hafen\": [\"Markt\", \"Park\"], \"Markt\": [\"Hafen\", \"Schule\", \"Bahnhof\"], \"Park\": [\"Hafen\", \"Bahnhof\"], \"Schule\": [\"Markt\", \"Stadion\"], \"Bahnhof\": [\"Markt\", \"Park\", \"Stadion\"], \"Stadion\": [\"Schule\", \"Bahnhof\"]}\nprint(\"Nachbarn von Markt:\", netz[\"Markt\"])\nabstand = {\"Hafen\": 0}\nschlange = [\"Hafen\"]\nwhile len(schlange) > 0:\n aktuell = schlange.pop(0)\n for nachbar in netz[aktuell]:\n if nachbar not in abstand:\n abstand[nachbar] = abstand[aktuell] + 1\n schlange.append(nachbar)\nprint(abstand)\n' > netz.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Breitensuche starten
docker exec jupyter python3 netz.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Beispiel: die Breitensuche ab Hafen
| Besucht | Neu in der Schlange | Abstand in Haltestellen |
|---|---|---|
| Hafen | Markt, Park | 0 |
| Markt | Schule, Bahnhof | Markt 1 |
| Park | nichts, Bahnhof war schon da | Park 1 |
| Schule | Stadion | Schule 2 |
| Bahnhof | nichts | Bahnhof 2 |
| Stadion | nichts | Stadion 3 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Den Weg findest du über die Vorgänger
Der Abstand sagt noch nicht, welchen Weg du fährst. Dafür merkst du dir zu jedem Knoten, von welchem er aus entdeckt wurde: seinen Vorgänger.
Am Ziel gehst du von Vorgänger zu Vorgänger zurück bis zum Start. Dreh die Liste um, und du hast den Weg.
Beispiel: der Weg vom Hafen zum Stadion
| Knoten | Vorgänger | Der Weg von hinten |
|---|---|---|
| Stadion | Schule | Stadion |
| Schule | Markt | Stadion, Schule |
| Markt | Hafen | Stadion, Schule, Markt |
| Hafen | keiner, der Start | Stadion, Schule, Markt, Hafen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele glauben, die Breitensuche finde die kürzeste Strecke in Kilometern. Sie zählt nur die Kanten, also die Haltestellen. Sind die Strecken verschieden lang, braucht man ein anderes Verfahren. Für gleich gewichtete Kanten stimmt sie.
Weiterführend: der Stapel statt der Schlange
Was ändert sich, wenn die Suche statt pop(0) das letzte Element mit pop() nimmt? Sie geht dann erst tief in einen Zweig hinein, bevor sie zum Nachbarn zurückkehrt. Das heißt Tiefensuche. Findet sie auch immer den kürzesten Weg?