main page — CS 566 Efficient Algorithms
Unit 9: Graph Algorithms
This is an archived version of this module from Winter 2024-25.
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
- Video 9-1 (2024-12-09, 21:37):
§9.1 Introduction & Graph Theory Definitions
- Video 9-2 (2024-12-09, 9:58):
§9.2 Graph Representations
- Video 9-3 (2024-12-10, 25:23):
§9.3 Graph Traversal
- Video 9-4 (2024-12-10, 31:37):
§9.4 BFS and DFS
- Video 9-5 (2024-12-10, 25:53):
§9.5 Advanced DFS: Topological Sorting
- Video 9-6 (2024-12-16, 39:27):
§9.5 Advanced DFS: Euler walks, Strongly connected components
- Video 9-7 (2024-12-16, 22:59):
§9.6 The max flow problem
- Video 9-8 (2024-12-16, 15:02):
§9.7 The Ford-Fulkerson method
- Video 9-9 (2024-12-17, 20:27):
§9.7 The Max-Flow Min-Cut Theorem
- Video 9-10 (2024-12-17, 24:58):
§9.8 The Edmonds-Karp Algorithm
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