Unit 11: Graphen

This unit covers fundamental graph algorithms

• graph terminology & definitions
• traversal, DFS, BFS
• connectivity, connected components
• DAGs & topological sorting

Material

• slides

• lecture notes

• Animationen:
  • Routing in Road Maps
  • Page Rank
  • de Bruijn Graphs
  • DFS
  • BFS
  • Directed DFS
  • Kosaraju-Sharir
  • Kruskal
  • Dijkstra
  • Graph editor
     
• Video 11-1 (2026-06-29): Graph-Anwendungen

• Video 11-2 (2026-06-29): Graphen Terminologie & Definitionen

• Video 11-3 (2026-06-29): Ungerichtete Graphen API

• Video 11-4 (2026-06-29): Repräsentationen von Graphen

• Video 11-5 (2026-06-29): Tiefensuche (Teil 1)

• Video 11-6 (2026-07-01): Tiefensuche (Teil 2)

• Video 11-7 (2026-07-01): Breitensuche, Zusammenhangskomponenten

• Video 11-8 (2026-07-01): Gerichtete Graphen

• Video 11-9 (2026-07-01): Topologisches Sortieren

• Video 11-10 (2026-07-06): Starke Zusammenhangskomponenten

• Video 11-11 (2026-07-06): Minimale Spannbäume

• Video 11-12 (2026-07-06): Kürzeste Wege

• Video 11-13 (2026-07-08): Dijkstras Algorithmus

Further sources

Motivation and graph definitions are my own presentation.

The presentation of the algorithms follows

• Sedgewick & Wayne, Algorithms, 4th Edition

• Video on Seam Carving
  Ariel Shamir Content Aware Image Resizing

• Routing (shortest paths) in practice
  Veritasium: Google Maps is unreasonably fast. Let me explain

---

Unit 10  ⋅  Syllabus  ⋅  Unit 12