[prev] 60 [next]

Depth-first Search (cont)

Cost analysis:
  • all vertices marked as unvisited, each vertex visited at most once ⇒ cost = O(V)
  • visit all edges incident on visited vertices ⇒ cost = O(E)
    • assuming an adjacency list representation
Time complexity of DFS: O(V+E)   (adjacency list representation)
  • the larger of V,E determines the complexity
For dense graphs … E ≅ V2 ⇒ O(V+E) = O(V2)
For sparse graphs … E ≅ V ⇒ O(V+E) = O(V)