Depth-first Search (cont)
Cost analysis:
- 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)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}