main page  —  CS 566 Efficient Algorithms

Unit 9: Graph Algorithms

This is an archived version of this module from Winter 2024-25.

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


Further reading and sources

Graph traversal and its applications are covered in many algorithms books. My presentation takes inspiration from the following sources:


Unit 8  ⋅  Syllabus  ⋅  Unit 10