main page — CS 566 Efficient Algorithms
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
- 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
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