Unit 9: Graph Algorithms

This unit covers widely used graph algorithms

• basic graph-search algorithms and their applications
• shortest paths
• minimum spanning trees
• network flows

Learning outcomes

1. Know basic terminology from graph theory, including types of graphs.
2. Know adjacency matrix and adjacency list representations and their performance characteristica.
3. Know graph-traversal based algorithm, including efficient implementations.
4. Be able to proof correctness of graph-traversal-based algorithms.
5. Know algorithms for maximum flows in networks.
6. Be able to model new algorithmic problems as graph problems.

Material

• slides (preliminary)

• lecture notes

• Video 9-1 (2025-12-08): §9.1 Introduction & Graph Theory Definitions

• Video 9-2 (2025-12-09): §9.2 Graph Representations

• Video 9-3 (2025-12-09): §9.3 Graph Traversal

• Video 9-4 (2025-12-09): §9.4 BFS

• Video 9-5 (2025-12-09): §9.5 DFS

• Video 9-6 (2025-12-09): §9.6 DFS Lemmas

---

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

---

Unit 8  ⋅  Syllabus  ⋅  Unit 10