← Informatik · Q2 · Thema 2.1
Netze aus Knoten und Kanten stecken in Straßenkarten, Rechnernetzen und Stundenplänen. Hier gibt es das Skript zum Nachlesen, eine Simulation zum Ausprobieren und die Übersicht, welches Verfahren welche Frage beantwortet.
BreitensucheTiefensucheDijkstra
Floyd / WarshallKruskalPrim
Topologische SortierungGale-Shapley
Inhalt des Skripts
- 1.1Was ist ein Graph?S. 2
- 1.2Erreichbarkeit: Warshall und FloydS. 4
- 1.3Breitensuche und TiefensucheS. 7
- 1.4Kürzeste Wege: DijkstraS. 9
- 1.5Minimaler Spannbaum: KruskalS. 11
- 1.6Minimaler Spannbaum: PrimS. 13
- 2Heiratsproblem und Gale-ShapleyS. 16
- 3Topologische SortierungS. 18
- 4Überblick: Welches Verfahren wofür?S. 19
- 5–6Übungen mit LösungenS. 21
Simulation
Verfahren wählen, Startknoten setzen und Schritt für Schritt verfolgen – mit derselben Tabelle wie im Unterricht.
⤢ Im Vollbild öffnenWelches Verfahren wofür?
| Verfahren | Frage | Idee | Datenstruktur | Laufzeit |
|---|---|---|---|---|
| Breitensuche | Welche Knoten sind erreichbar? Weg mit den wenigsten Kanten? | schichtweise vom Start aus | Queue | O(n+m) |
| Tiefensuche | Welche Knoten sind erreichbar? Gibt es Zyklen? | so tief wie möglich, dann zurück | Stack (oder Rekursion) | O(n+m) |
| Dijkstra | kürzeste Wege von einem Start (Gewichte ≥ 0) | immer den nächstgelegenen offenen Knoten festlegen | Prioritätswarteschlange | O((n+m) log n) |
| Floyd | kürzeste Wege zwischen allen Paaren | Umweg über jeden Zwischenknoten k prüfen | Matrix | O(n³) |
| Warshall | Wer erreicht wen? | wie Floyd, nur mit 0/1 | Matrix | O(n³) |
| Kruskal | minimaler Spannbaum | leichteste Kante ohne Zyklus, Teilbäume vereinigen | sortierte Kanten, Union-Find | O(m log m) |
| Prim | minimaler Spannbaum | einen Baum über die leichteste Randkante wachsen lassen | Heap | O(m log m) |
| Kahn | Reihenfolge mit Abhängigkeiten (gerichtet, azyklisch) | Knoten mit Eingangsgrad 0 zuerst | Liste/Queue, Eingangsgrade | O(n+m) |
| Gale-Shapley | stabile Paarung zweier Gruppen | Anträge nach Präferenz, Verlobung lösbar | Präferenzlisten | O(n²) |
n = Anzahl der Knoten, m = Anzahl der Kanten.