Recitation 12

From 6.006 Introduction to Algorithms

Jump to: navigation, search

BFS vs DFS

  • BFS
    • Finds Shortest Paths
    • Start Node is important
    • Creates a Breadth First/Shortest Paths Tree
  • DFS
    • Finishing Times
    • Can be used to Topological Sort
    • Might need multiple "start" nodes
    • Creates a Depth First Forest
  • Both BFS and DFS
    • Finds every vertex
    • Θ(V + E) time
    • Θ(V) space
Retrieved from "http://6.006.scripts.mit.edu/~6.006/spring08/wiki/index.php?title=Recitation_12"
Personal tools