[Solved] Why do DFS run in O(V+E) if the graph is stored as Adajacency List? [closed]

Question

Depth First Search or DFS as it is more generally called is a graph/tree traversing algorithm.

How It Works

Consider a graph such as given below

Now let’s dig deep into how these numbers are coming up.

We start with the starting node and mark it as visited then we add it to the top of the stack. We always look for non-visited neighbors of element at top of the stack.

After first step :

Stack = A
Output = A
Visited = A

Now we have 3 neighbors to A, we can choose any one of the neighbor if no order is provided in which they are to be chosen. We move to B and push it to the top of the stack and mark it as visited and add to the sequence.

Stack = A,B
Output = A,B
Visited = A,B

Now B has only two neighbors again so we move to it’s next neighbor, move it to the top of the stack, add it to the sequence and mark it as visited.

Stack = A,B,D
Output = A,B,D
Visited = A,B,D

Now D has no more neighbors and is the leaf node, so we pop D from the top of the stack.

Stack = A,B
Output = A,B,D
Visited = A,B,D

Now we have B at the top of the stack, we already have visited D so we move onto it’s next neighbor is F, so we add F to the top of the stack, mark it as visited and add it to the sequence.

Stack = A,B,F
Output = A,B,D,F
Visited = A,B,D,F

Now F has only one neighbor so we move on to it. We follow the same procedure for node E which gives

Stack = A,B,F,E
Output = A,B,D,F,E
Visited = A,B,D,F,E

Now, the immediate neighbor node of E is A but we have already visited A and have no where to go from E so we pop it from the top of the stack.

Stack = A,B,F
Output = A,B,D,F,E
Visited = A,B,D,F,E

Similarly we have visited all the neighbors of F too hence we pop F from the top of the stack.

Stack = A,B
Output = A,B,D,F,E
Visited = A,B,D,F,E

We have no path to traverse from B as well hence we pop B from the stack too

Stack = A
Output = A,B,D,F,E
Visited = A,B,D,F,E

Now the next neighbor to A is C, so we add C to the top of the stack and mark it as visited.

Stack = A,C
Output = A,B,D,F,E,C
Visited = A,B,D,F,E,C

G is the immediate neighbor to our node C, hence we add it to the top of the stack and mark it as visited

Stack = A,C,G
Output = A,B,D,F,E,C,G
Visited = A,B,D,F,E,C,G

Since G is the leaf node we have no path from it so we pop it from the stack

Stack = A,C
Output = A,B,D,F,E,C,G
Visited = A,B,D,F,E,C,G

Since we have traversed all the nodes off C as well we pop it from the stack too

Stack = A
Output = A,B,D,F,E,C,G
Visited = A,B,D,F,E,C,G

The next neighbor to A is E but we have marked it already as visited hence we are left with no path from A so we pop A from the stack and the stack gets empty giving us the DFS sequence.

Stack = null
Output = A,B,D,F,E,C,G
Visited = A,B,D,F,E,C,G

PS: Sorry for any grammatical errors

Accepted Answer