Graphs

Graphs

Graph Search

Explore a graph, e.g:

• find a path from start vertex s to a desired vertex
• visit all vertices or edge of graph, or only those reachable from s

  Graph Representations

  

  Breadth First Search

• level 0={s}
• level = vertices reachable by path of i edges but not fewer
• build level i>0 from level i-1 by trying all outgoing edges, but ignoring vertices from previous levels
• O(V+E) (Linear time)

  Shortest Paths

  

  Depth First Search

  

  Cycle Detection

  Graph G has a cycle <=> DFS has a back edge

Source

https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/pages/lecture-notes/