Graphen
Die Struktur hinter Karten, Netzwerken und Abhängigkeiten.
Graphen verallgemeinern Bäume zu beliebigen Netzwerken - Straßen, soziale Verbindungen, Aufgabenabhängigkeiten. Lerne sie darzustellen, mit BFS und DFS zu durchlaufen, kürzeste Wege zu finden, Abhängigkeiten topologisch zu sortieren und Komponenten mit Union-Find zu gruppieren.
Lektionen in dieser Stufe
- 01
Einen Graphen darstellen
FortgeschrittenAdjazenzliste vs. Adjazenzmatrix, gerichtet vs. ungerichtet, gewichtet vs. ungewichtet - und wie man ein Problem überhaupt als Graph modelliert.
14 Min. - 02
BFS & DFS
ExperteDie zwei grundlegenden Traversierungen: Breitensuche für kürzeste ungewichtete Wege und Ebenen, Tiefensuche für Zusammenhang - mit einer Visited-Menge gegen Zyklen.
17 Min. - 03
Gitter als Graphen
FortgeschrittenInseln zählen, Flood Fill, kürzester Weg im Labyrinth - 2D-Gitter sind Graphen, in denen jede Zelle mit ihren Nachbarn verbunden ist, und BFS/DFS lösen sie direkt.
14 Min. - 04
Topologische Sortierung
ExperteAufgaben so ordnen, dass jede Abhängigkeit zuerst kommt - Stundenpläne, Build-Systeme - und wie sie dabei Zyklen erkennt.
15 Min. - 05
Kürzeste Wege & Union-Find
ExperteDijkstra für gewichtete kürzeste Wege und Union-Find (disjunkte Mengen) für Zusammenhang und Gruppierung in nahezu konstanter Zeit.
16 Min.