Wie findet eine App den kürzesten Weg?
Die Breitensuche findet in einem Netz aus Punkten und Verbindungen den Weg mit den wenigsten Schritten. Sie arbeitet in Navigations-Apps, bei Freundschaftsvorschlägen und beim Prüfen, ob zwei Rechner im Netz verbunden sind.
Ein Nahverkehrsnetz hat sieben Haltestellen und acht Direktverbindungen. Gesucht ist die Fahrt mit den wenigsten Fahrten dazwischen.
Am Ende dieser Lektion
Notiz
Ich kann mit der Breitensuche einen Weg mit den wenigsten Schritten in einem Graphen finden.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Graph | Punkte, die durch Linien verbunden sind | |
| Knoten | ein Punkt im Graphen | Markt |
| Kante | eine Linie zwischen zwei Knoten | |
| Warteschlange | hinten anstellen, vorn herausnehmen | |
| Besucht | ein Knoten, der schon gesehen wurde |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Graph besteht aus Knoten und Kanten
Ein Graph besteht aus Knoten und Kanten. Im Nahverkehrsnetz ist jede Haltestelle ein Knoten und jede Direktverbindung eine Kante.
In Python merken wir uns zu jedem Knoten die Liste seiner Nachbarn in einem Wörterbuch. Zwei Knoten sind Nachbarn, wenn eine Kante sie verbindet.
Das Netz: jede Haltestelle mit ihren Nachbarn
| Haltestelle | Nachbarn |
|---|---|
| Markt | Dom, Hafen |
| Dom | Markt, Park, Uni |
| Hafen | Markt, Werk |
| Park | Dom, Uni |
| Uni | Dom, Park, Bahnhof |
| Bahnhof | Uni, Werk |
| Werk | Hafen, Bahnhof |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Das Netz als Wörterbuch
# Ein Haltestellennetz: zu jeder Haltestelle die Liste ihrer Nachbarn.
netz = {
"Markt": ["Dom", "Hafen"],
"Dom": ["Markt", "Park", "Uni"],
"Hafen": ["Markt", "Werk"],
"Park": ["Dom", "Uni"],
"Uni": ["Dom", "Park", "Bahnhof"],
"Bahnhof": ["Uni", "Werk"],
"Werk": ["Hafen", "Bahnhof"],
}
for name in netz:
print(name, "hat", len(netz[name]), "Nachbarn:", netz[name])
# Fuegen Sie eine Haltestelle "Strand" hinzu, die nur mit "Hafen" verbunden ist.
Die Breitensuche geht Ring für Ring nach außen
Die Breitensuche besucht zuerst alle Nachbarn des Starts, dann deren Nachbarn, und so weiter. Sie merkt sich dafür eine Warteschlange: Wer zuerst angestellt wurde, kommt zuerst dran.
Jeder Knoten bekommt beim ersten Besuch seinen Abstand: den des Vorgängers plus 1. Ein besuchter Knoten wird nie wieder angestellt. So endet die Suche auch in einem Netz mit Kreisen.
Die Breitensuche vom Markt aus
| Runde | Herausgenommen | Neu angestellt | Warteschlange danach |
|---|---|---|---|
| 1 | Markt (0) | Dom (1), Hafen (1) | Dom, Hafen |
| 2 | Dom | Park (2), Uni (2) | Hafen, Park, Uni |
| 3 | Hafen | Werk (2) | Park, Uni, Werk |
| 4 | Park | nichts | Uni, Werk |
| 5 | Uni | Bahnhof (3) | Werk, Bahnhof |
| 6 | Werk | nichts | Bahnhof |
| 7 | Bahnhof | nichts | leer |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Abstände vom Markt aus
# Breitensuche: erst alle Nachbarn, dann deren Nachbarn, und so weiter.
netz = {
"Markt": ["Dom", "Hafen"],
"Dom": ["Markt", "Park", "Uni"],
"Hafen": ["Markt", "Werk"],
"Park": ["Dom", "Uni"],
"Uni": ["Dom", "Park", "Bahnhof"],
"Bahnhof": ["Uni", "Werk"],
"Werk": ["Hafen", "Bahnhof"],
"Insel": [],
}
start = "Markt"
abstand = {start: 0}
warteschlange = [start]
while len(warteschlange) > 0:
aktuell = warteschlange.pop(0) # vorn herausnehmen: wer zuerst kam
for nachbar in netz[aktuell]:
if nachbar not in abstand: # nur unbesuchte Haltestellen
abstand[nachbar] = abstand[aktuell] + 1
warteschlange.append(nachbar) # hinten anstellen
for name in netz:
if name in abstand:
print(name, abstand[name])
else:
print(name, "nicht erreichbar")
# Aendern Sie start auf "Bahnhof" und vergleichen Sie die Abstaende.
Die Breitensuche zählt Schritte, nicht Minuten
Die Breitensuche findet den Weg mit den wenigsten Kanten. Sie weiß nichts über die Dauer einer Kante.
Ein Weg mit zwei Kanten zu je 20 und 25 Minuten dauert 45 Minuten. Ein Weg mit drei Kanten zu 5, 5 und 10 Minuten dauert nur 20. Für den billigsten Weg braucht man ein Verfahren mit Kosten, das ein späteres Modul zeigt.
Im Lab: das Netz als Liste von Verbindungen
Als Textdatei steht jede Direktverbindung in einer Zeile, zwei Namen mit einem Leerzeichen. Der Befehl printf schreibt solche Zeilen für das Netz von oben.
Die Befehle zählen daraus die Kanten, die Knoten und die Nachbarn jedes Knotens. So prüfen Sie die Tabelle am Terminal.
Die Kanten zählen
printf "Markt Dom\nMarkt Hafen\nDom Park\nDom Uni\nPark Uni\nUni Bahnhof\nHafen Werk\nWerk Bahnhof\n" | wc -lHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Knoten zählen
printf "Markt Dom\nMarkt Hafen\nDom Park\nDom Uni\nPark Uni\nUni Bahnhof\nHafen Werk\nWerk Bahnhof\n" | tr ' ' '\n' | sort -u | wc -lHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Nachbarn jedes Knotens zählen
printf "Markt Dom\nMarkt Hafen\nDom Park\nDom Uni\nPark Uni\nUni Bahnhof\nHafen Werk\nWerk Bahnhof\n" | tr ' ' '\n' | sort | uniq -cHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele denken, die Breitensuche finde die schnellste Fahrt. Sie findet die mit den wenigsten Kanten. Haben die Kanten unterschiedliche Dauer, kann ein Weg mit mehr Kanten schneller sein. Bei gleichen Kanten stimmt beides überein.
Weiterführend
Ändern Sie die Funktion so, dass sie nicht die Zahl, sondern den Weg als Liste der Haltestellen zurückgibt. Merken Sie sich dafür zu jedem Knoten den Vorgänger.
Gehen Sie vom Ziel über die Vorgänger zurück zum Start und drehen Sie die Liste um. Probieren Sie es von Markt nach Bahnhof.