[prev] 61 [next]

Depth-first Search (cont)

Note how different graph data structures affect cost:
  • array-of-edges representation
    • visit all edges incident on visited vertices ⇒ cost = O(V·E)
    • cost of DFS: O(V·E)
  • adjacency-matrix representation
    • visit all edges incident on visited vertices ⇒ cost = O(V2)
    • cost of DFS: O(V2)