main page — CS 566 Efficient Algorithms
Unit 9: Graph Algorithms
This is an archived version of this module from Winter 2025-26.
Click here for the current iteration.
This unit covers widely used graph algorithms
- basic graph-search algorithms and their applications
- shortest paths
- minimum spanning trees
- network flows
Learning outcomes
- Know basic terminology from graph theory, including types of graphs.
- Know adjacency matrix and adjacency list representations and their performance characteristica.
- Know graph-traversal based algorithm, including efficient implementations.
- Be able to proof correctness of graph-traversal-based algorithms.
- Know algorithms for maximum flows in networks.
- Be able to model new algorithmic problems as graph problems.
Material
- slides (preliminary)
- Video 9-1 (2025-12-08, 21:20):
§9.1 Introduction & Graph Theory Definitions
- Video 9-2 (2025-12-09, 10:03):
§9.2 Graph Representations
- Video 9-3 (2025-12-09, 21:20):
§9.3 Graph Traversal
- Video 9-4 (2025-12-09, 21:57):
§9.4 BFS
- Video 9-5 (2025-12-09, 13:46):
§9.5 DFS
- Video 9-6 (2025-12-09, 6:36):
§9.6 DFS Lemmas
- Video 9-7 (2025-12-15, 39:27):
§9.6 DFS edge types, Cycle detection
- Video 9-8 (2025-12-15, 39:00):
§9.7 Hierholzer’s algorithm, Kosaraju-Sharir
- Video 9-9 (2025-12-16, 27:06):
§9.8 The max flow problem
- Video 9-10 (2025-12-16, 38:54):
§9.9 The Ford-Fulkerson method
- Video 9-11 (2025-12-17, 7:48):
§9.10 The Edmonds-Karp algorithm
- Video 9-12 (2024-01-12, 21:53):
§9.10 Edmonds-Karp analysis
Further reading and sources
Graph traversal and its applications are covered in many algorithms books. My presentation takes inspiration from the following sources:
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2009), MIT Press
- Sedgewick, Wayne: Algorithms 4th ed (2011), Pearson
- Myers, Kozen: Object-Oriented Design and Data Structures lecture notes