Graphen: BFS, DFS, topologische Sortierung und Dijkstra

Track Konzepte · Algorithmen · ca. 50 Min.

Worum es geht

Ein Monorepo hat 200 Module, und jedes sagt, welche anderen vorher gebaut sein müssen. Der Build-Server braucht eine Reihenfolge, in der nie ein Modul vor seinen Voraussetzungen kommt. Gibt es sie immer? Nein: Bauen A und B sich gegenseitig, gibt es keine, und ein guter Build meldet das, statt sich aufzuhängen. Dieselbe Denkweise steckt hinter Routenplanung und Netzwerk-Latenzen. Es ist immer ein Graph (graph).

Am Ende von Teil a kannst du:

eine topologische Sortierung (topological sort) bauen, die bei einem Zyklus sauber scheitert (Übung 1),
mit BFS (breadth-first search, Breitensuche) den kürzesten Weg in einem Gitter finden (Übung 2),
mit Dijkstra und einer Priority Queue gewichtete kürzeste Wege berechnen (Übung 3).

Teil b (Union-Find und Entwurfstechniken) behandelt Union-Find, Dynamic Programming und die Greedy-Falle.

Nicht Thema: Datenstrukturen selbst (Hashmap, Heap, Big O) stehen in Lektion 20. Zyklen als Deadlock im Wait-for-Graph zeigt Lektion 3, den Import-Graphen eines Projekts per ast baust du in Lektion 11. Hier lernst du die Algorithmen dahinter.

Plane ehrlich 50 Minuten ein: etwa 20 Minuten Lesen, 27 Minuten Übungen (drei Stück).

Von JS/TS her gedacht

In JS/TS hast du dafür keine Standardbibliothek: Graphen sind bei dir meist Map oder Objekt von Knoten zu Nachbarlisten, eine Queue ist ein Array mit shift(), und eine Priority Queue gibt es nur als npm-Paket. In Python liegt mehr fertig bereit:

Baustein	JS/TS	Python
Graph (Adjazenzliste)	`Record<string, string[]>` oder `Map`	`dict` von Knoten zu Liste
Queue für BFS	Array mit `shift()` (O(n)) oder selbst gebaut	`collections.deque` mit `popleft()`
Stack für DFS	Array mit `push` und `pop`	`list` mit `append` und `pop`
Priority Queue für Dijkstra	Paket oder selbst gebaut	`heapq` (Min-Heap)
“schon gesehen”	`Set`	`set` oder `dict`

Dieselbe Idee in beiden Sprachen: Kahn-Verfahren für die Build-Reihenfolge. JavaScript, mit Node ausgeführt (TypeScript wäre derselbe Code mit Typen):

const abh = { app: ["auth", "db"], auth: ["db", "utils"], db: ["utils"], utils: [] };
function kahn(abh) {
  const offen = new Map();       // Modul -> Zahl noch offener Voraussetzungen
  const nachfolger = new Map();  // Modul -> Module, die auf es warten
  for (const [m, vs] of Object.entries(abh)) {
    offen.set(m, (offen.get(m) ?? 0) + vs.length);
    for (const v of vs) {
      if (!offen.has(v)) offen.set(v, 0);
      nachfolger.set(v, [...(nachfolger.get(v) ?? []), m]);
    }
  }
  const bereit = [...offen].filter(([, n]) => n === 0).map(([m]) => m);
  const reihenfolge = [];
  while (bereit.length) {
    const m = bereit.pop();
    reihenfolge.push(m);
    for (const nf of nachfolger.get(m) ?? []) {
      offen.set(nf, offen.get(nf) - 1);
      if (offen.get(nf) === 0) bereit.push(nf);
    }
  }
  if (reihenfolge.length < offen.size) throw new Error("Zyklus");
  return reihenfolge;
}
console.log(kahn(abh));
try { kahn({ app: ["auth"], auth: ["app"], utils: [] }); } catch (e) { console.log(e.message); }

Ausgabe:

[ 'utils', 'db', 'auth', 'app' ]
Zyklus

Die Python-Fassung steht gleich in Schritt 2. Sie ist fast Zeile für Zeile dieselbe.

Konzept

Schritt 1: Graph, BFS und DFS

Ein Graph besteht aus Knoten (nodes) und Kanten (edges). Gerichtet (directed) heißt: eine Kante hat eine Richtung, “A braucht B”. Als Python-Datenstruktur nimmst du die Adjazenzliste (adjacency list): ein dict, das zu jedem Knoten seine Nachbarn nennt. Das Beispiel ist ein Follower-Graph: anna folgt bora und cem und so weiter.

Zwei Arten, den Graphen systematisch abzulaufen:

BFS (Breitensuche) geht Ebene für Ebene vor, mit einer Queue (FIFO): erst alle Nachbarn, dann deren Nachbarn. Dadurch findet sie bei ungewichteten Kanten den kürzesten Weg (wenigste Kanten).
DFS (depth-first search, Tiefensuche) geht so weit wie möglich einen Pfad entlang und kehrt erst dann um, mit einem Stack (LIFO) oder mit Rekursion. Sie ist die Grundlage für Zyklenerkennung und viele andere Verfahren, liefert aber nicht den kürzesten Weg.

Ausgabe:

{'anna': 0, 'bora': 1, 'cem': 1, 'dilan': 2, 'emre': 2, 'fatma': 3}
['anna', 'bora', 'dilan', 'fatma', 'cem', 'emre']

Lies BFS: bora und cem sind einen Schritt von anna entfernt, dilan und emre zwei, fatma drei. dilan ist über bora und über cem erreichbar, wird aber nur beim ersten Mal eingetragen. Genau dafür ist das Wörterbuch abstand: Ohne “schon gesehen” liefe BFS bei Zyklen endlos. Die DFS-Reihenfolge geht erst ganz in die Tiefe (anna, bora, dilan, fatma) und kommt dann zu cem. Beide Verfahren besuchen jeden Knoten und jede Kante einmal: Kosten O(V + E) (V Knoten, E Kanten).

Mini-Fallen: Eine Liste mit pop(0) als Queue macht BFS quadratisch (Lektion 20), darum deque. Und “schon gesehen” gehört in die Schleife vor dem Einreihen, sonst landet derselbe Knoten mehrfach in der Queue.

Schritt 2: Topologische Sortierung (Kahn)

Eine topologische Sortierung ordnet die Knoten eines gerichteten Graphen ohne Zyklus (DAG, directed acyclic graph) so, dass jede Kante von früher nach später zeigt. Beim Build: kein Modul steht vor seinen Voraussetzungen. Das Kahn-Verfahren (Kahn’s algorithm) macht das so:

Zähle für jeden Knoten, wie viele Voraussetzungen noch offen sind.
Alle Knoten mit 0 offenen Voraussetzungen sind bereit.
Nimm einen bereiten Knoten, hänge ihn an die Ausgabe an und senke den Zähler aller Knoten, die auf ihn warten. Wer auf 0 fällt, wird bereit.
Wiederhole, bis nichts mehr bereit ist.

Bleibt am Ende Rest übrig (Ausgabe kürzer als die Knotenzahl), gibt es einen Zyklus: Die Knoten im Zyklus warten ewig aufeinander, ihr Zähler wird nie 0.

Ausgabe:

['utils', 'db', 'auth', 'app']
Zyklus, nicht baubar: ['app', 'auth', 'db']

Gehe den ersten Fall durch: utils hat keine Voraussetzung und ist bereit. Nach utils fällt der Zähler von db auf 0, dann auth (braucht db und utils), dann app. Im zweiten Fall bauen sich auth und db gegenseitig. Nur utils kommt durch. Im Rest steht außerdem app: Es ist nicht Teil des Zyklus, wartet aber auf auth. Der Rest ist also “Zyklus plus alles, was daran hängt”. Zwei Details, die dir in Übung 1 begegnen: setdefault(v, 0) nimmt Knoten auf, die nur als Voraussetzung vorkommen (nie als Schlüssel), und bereit.pop() nimmt den zuletzt bereit gewordenen. Welche Ordnung bei Gleichstand entsteht, hängt vom Datentyp für bereit ab. Wer eine reproduzierbare Reihenfolge braucht (gleicher Build auf jedem Rechner), muss die Regel festlegen. Ein Werkzeug dafür ist heapq (Min-Heap aus Lektion 20): heapq.heapify(liste) macht eine Liste zum Heap, heapq.heappush(liste, x) fügt ein Element ein, heapq.heappop(liste) entnimmt immer das kleinste (bei Strings das alphabetisch erste, bei Tupeln wird das erste Feld zuerst verglichen). Du siehst es gleich in Schritt 3 bei Dijkstra im Einsatz, und in Übung 1 brauchst du es.

Alternative: Eine DFS, die einen Knoten nach allen Voraussetzungen ausgibt, und dabei Knoten auf dem aktuellen Pfad markiert. Trifft sie einen markierten Knoten, ist das ein Zyklus. Beides ist O(V + E). Dieselbe Zyklussuche kennst du aus dem Wait-for-Graph in Lektion 3: Zyklus im Graphen heißt “alle warten aufeinander”.

Kurz zum Rest der Familie, ohne Übung: Starke Zusammenhangskomponenten (strongly connected components, SCC, Verfahren von Tarjan oder Kosaraju) finden in einem Graphen mit Zyklen alle Gruppen, in denen jeder jeden erreicht. Fasst man jede Gruppe zu einem Knoten zusammen, entsteht wieder ein DAG, den man topologisch sortieren kann. So zeigen Build-Werkzeuge zyklische Modulgruppen an.

Schritt 3: Dijkstra, kürzeste Wege mit Gewichten

BFS zählt Kanten. Sind die Kanten gewichtet (weighted, Kosten, Entfernung, Latenz), ist der Weg mit den wenigsten Kanten nicht der billigste. Dijkstra löst das für nicht negative Gewichte:

Eine Priority Queue (Python: heapq) enthält Paare (Kosten bis hier, Knoten). Start: (0, start).
Hole das Paar mit den kleinsten Kosten. Ist der Knoten schon fertig, überspringe es.
Sonst sind diese Kosten endgültig (kein anderer Weg kann billiger sein, denn alle übrigen Wege sind schon mindestens so teuer und Gewichte sind nie negativ). Trage sie ein.
Lege für jeden Nachbarn (Kosten + Gewicht, Nachbar) in die Queue.

Ausgabe: {'A': 0, 'C': 2, 'B': 5, 'D': 6}. Gehe es durch: Von A aus kostet B direkt 7, aber über C nur 2 + 3 = 5. D kostet über B 5 + 1 = 6, direkt von C 2 + 8 = 10. Die kürzeste Kantenzahl wäre bei D jeweils 2, aber nur eine der Routen ist billig. E fehlt im Ergebnis: Man kommt von A aus nicht zu E (die Kante zeigt in die andere Richtung). Nicht erreichbare Knoten tauchen im Ergebnis nicht auf. Der Eintrag knoten in kosten oben ist ein Standardtrick: Ein Knoten darf mehrfach in der Queue liegen, nur der erste Treffer zählt (statt Einträge in der Queue zu ändern).

Kosten: O((V + E) log V). Negative Gewichte brechen die Garantie “Kosten beim Herausnehmen sind endgültig” (dafür gibt es Bellman-Ford, hier nicht). A* ist Dijkstra mit einer Schätzung (heuristic) der Restkosten zum Ziel: Die Queue sortiert nach “Kosten bisher plus Schätzung” und läuft so zielgerichteter, etwa auf Karten (allgemeines Fachwissen, kein Code hier).

Falle

Kein “schon gesehen” bei BFS und DFS. Bei Zyklen läuft das Programm endlos oder besucht Knoten mehrfach (O(V + E) wird exponentiell).
DFS für den kürzesten Weg. Sie findet einen Weg, nicht den kürzesten (Übung 2).
BFS bei gewichteten Kanten. Die wenigsten Kanten sind nicht die geringsten Kosten (Übung 3).
Dijkstra mit “fertig” beim Einreihen statt beim Herausnehmen. Der erste gefundene Weg zu einem Knoten ist nicht der billigste. Und Dijkstra mit negativen Gewichten liefert falsche Ergebnisse.
Zyklus ignorieren. Eine Build-Reihenfolge, die bei einem Zyklus stillschweigend eine kürzere Liste zurückgibt, baut zu wenig und merkt es nicht (Übung 1).

Übungen

Übung 1: Build-Reihenfolge mit Zyklenerkennung (ca. 10 Min.)

Eine Datenbank wird über Migrationen aufgebaut, und jede Migration kann von anderen abhängen. Schreibe build_reihenfolge(abhaengigkeiten). abhaengigkeiten ist ein dict: Schlüssel ist ein Name, Wert die Liste der Namen, die vorher laufen müssen.

Regeln:

Gib eine Liste aller Namen zurück, in einer gültigen Reihenfolge. Namen, die nur als Voraussetzung vorkommen (nicht als Schlüssel), gehören dazu.
Gleichstand: Von allen Namen, die gerade laufen können, kommt der alphabetisch kleinste zuerst. Damit ist die Reihenfolge eindeutig.
Bei einem Zyklus wirfst du ValueError.
Das übergebene dict und seine Listen werden nicht verändert.
Ein leeres dict ergibt [].

Beispiel: {"c": [], "d": [], "b": ["d"], "a": ["c"]} ergibt ["c", "a", "d", "b"] (erst c, dann ist a bereit und kleiner als d).

Die letzte Zeile gibt die Funktion zurück.

import heapq

def build_reihenfolge(abhaengigkeiten):
    offen = {}
    folgen = {}
    for modul, voraussetzungen in abhaengigkeiten.items():
        offen.setdefault(modul, 0)
        for v in voraussetzungen:
            offen[modul] += 1
            offen.setdefault(v, 0)
            folgen.setdefault(v, []).append(modul)
    bereit = [m for m, n in offen.items() if n == 0]
    heapq.heapify(bereit)
    reihenfolge = []
    while bereit:
        m = heapq.heappop(bereit)
        reihenfolge.append(m)
        for f in folgen.get(m, []):
            offen[f] -= 1
            if offen[f] == 0:
                heapq.heappush(bereit, f)
    if len(reihenfolge) < len(offen):
        raise ValueError("Zyklus")
    return reihenfolge

build_reihenfolge

Kahn mit einem Min-Heap statt einer Liste als Menge der bereiten Namen: heappop liefert immer den alphabetisch kleinsten. Der Zyklus zeigt sich daran, dass weniger Namen ausgegeben wurden, als es gibt. Eine DFS mit Nachordnung ginge auch, bräuchte aber extra Arbeit für die Regel “alphabetisch kleinster zuerst”.

Übung 2: Kürzester Weg im Gitter mit BFS (ca. 7 Min.)

Ein Lagerroboter fährt in einem Gitter. gitter ist eine Liste von Strings, . ist frei, # ist eine Wand. Der Roboter geht pro Schritt ein Feld nach oben, unten, links oder rechts (nicht diagonal). Schreibe kuerzester_weg(gitter, start, ziel) mit start und ziel als (zeile, spalte). Rückgabe: die Anzahl Schritte des kürzesten Weges.

Randfälle:

start == ziel ergibt 0.
Gibt es keinen Weg, ergibt es None.
Liegt Start oder Ziel auf einer Wand, ergibt es None.
Am Rand des Gitters darf nichts fehlschlagen. Wichtig in Python: Der Index -1 ist gültig und springt ans Ende, ohne Fehler.

Beispiel: kuerzester_weg(["..#", ".#.", "..."], (0, 0), (2, 2)) ergibt 4. Der Check testet auch ein Gitter mit 14400 Feldern.

from collections import deque

def kuerzester_weg(gitter, start, ziel):
    hoehe, breite = len(gitter), len(gitter[0]) if gitter else 0
    def frei(z, s):
        return 0 <= z < hoehe and 0 <= s < breite and gitter[z][s] != "#"
    if not frei(*start) or not frei(*ziel):
        return None
    abstand = {start: 0}
    warteschlange = deque([start])
    while warteschlange:
        z, s = warteschlange.popleft()
        if (z, s) == ziel:
            return abstand[(z, s)]
        for dz, ds in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nachbar = (z + dz, s + ds)
            if frei(*nachbar) and nachbar not in abstand:
                abstand[nachbar] = abstand[(z, s)] + 1
                warteschlange.append(nachbar)
    return None

kuerzester_weg

BFS in Ebenen: Beim ersten Erreichen des Ziels sind es garantiert die wenigsten Schritte. Die Prüfung 0 <= z < hoehe verhindert den Rand-Fehler und den Python-Sprung durch negative Indizes. Das Wörterbuch abstand ist zugleich “schon gesehen”.

Übung 3: Dijkstra mit heapq (ca. 10 Min.)

Ein Netzwerk verbindet Rechenzentren, jede gerichtete Verbindung hat eine Latenz in Millisekunden (ganze Zahl, 0 oder größer). Schreibe kuerzeste_latenzen(netz, start). netz ist ein dict von Knoten zu einer Liste von (nachbar, latenz). Rückgabe: ein dict von jedem erreichbaren Knoten (inklusive start, mit 0) zu den niedrigsten Gesamtkosten.

Randfälle:

Nicht erreichbare Knoten fehlen im Ergebnis.
Knoten, die nur als Ziel einer Kante vorkommen (nicht als Schlüssel), sind erlaubt.
Steht start selbst nicht in netz, ist das Ergebnis {start: 0}.
Latenz 0 und mehrere gleich teure Wege kommen vor.
netz bleibt unverändert.

Beispiel: {"fra": [("ams", 9), ("par", 5)], "par": [("ams", 3)], "ams": []} mit Start "fra" ergibt {"fra": 0, "par": 5, "ams": 8}.

import heapq

def kuerzeste_latenzen(netz, start):
    kosten = {}
    heap = [(0, start)]
    while heap:
        k, knoten = heapq.heappop(heap)
        if knoten in kosten:
            continue
        kosten[knoten] = k
        for nachbar, latenz in netz.get(knoten, []):
            if nachbar not in kosten:
                heapq.heappush(heap, (k + latenz, nachbar))
    return kosten

kuerzeste_latenzen

Die Kosten eines Knotens sind endgültig, wenn er zum ersten Mal aus der Queue kommt, nicht beim Einreihen. Veraltete Einträge (zweites Herauskommen) werden übersprungen. netz.get(knoten, []) deckt Knoten ab, die nur als Ziel vorkommen. Nicht erreichbare Knoten werden nie eingetragen.

Merksatz

Ein Graph beantwortet Fragen über Beziehungen: BFS den kürzesten Weg ohne Gewichte, Dijkstra den billigsten mit Gewichten, die topologische Sortierung eine gültige Reihenfolge (und bei einem Zyklus keine).

Prüfstein

Wie ermittelst du eine Build-Reihenfolge für 200 Module mit Abhängigkeiten, und was passiert bei einem Zyklus? Nenne ein Verfahren, seine Laufzeit und wie du den Zyklus erkennst.
Wann reicht BFS für den kürzesten Weg, wann brauchst du Dijkstra, und was darf bei Dijkstra nicht vorkommen?

Weiter mit Teil b: Union-Find und Entwurfstechniken.

Quelle: quellen/konzeptuebersicht-software-grundlagen.md, Abschnitt “2. Datenstrukturen und Algorithmen” (Standardalgorithmen, Graph-Traversierung BFS und DFS). quellen/konzeptuebersicht-software-fortgeschritten.docx, Abschnitt “2. Algorithmen und Datenstrukturen im Einsatz” (Graphalgorithmen: Dijkstra, A*, topologische Sortierung, starke Zusammenhangskomponenten; Prüfstein zur Build-Reihenfolge).

Über die Quelle hinaus (allgemeines Fachwissen): die Beschreibung des Kahn-Verfahrens und der DFS-Variante, die Laufzeiten O(V + E) und O((V + E) log V), die Begründung der Dijkstra-Korrektheit und die Einschränkung auf nicht negative Gewichte (Bellman-Ford als Alternative), die Erklärung von A* und SCC (Tarjan, Kosaraju). Alle Zahlen und Ausgaben in dieser Lektion stammen aus dem Ausführen des Codes mit Python 3 bzw. Node.