算法复习

course algorithm

Graph Algorithms

Algorithm on Graphs

  • elementary graph algorithms
    1. breadth-first search
    2. depth-first search
    3. minimum spanning tree
  • shortest path problem
    1. single-source shortest path
    2. all-pairs shortest path
  • maximum flow
    1. max-flow vs min-cut
    2. applications

DFS

time complexity: O(|V|+|E|)