The algorithm:

This is an algorithm that is used to traverse a graph Depth-wise. We move forward in depth and visit all the adjacent nodes of a given starting node. We then visit the adjacent nodes of those. However, this poses a problem. In a graph, there is a possibility of loops. This would result in an infinite loop as we would keep visiting the same node. To get past this problem, we will have to use a boolean visited array. This marks nodes as visited so that we do not visit them again.

To visualise this algorithm, we use a graph, a stack data structure, a boolean visited array and an output array.

For example:

Consider the following graph:

Using depth first traversal, we start at node 0. We add 0 to the stack and the output array. We also mark it as visited in the boolean array.

Stack = [0]    

Output array = [0]   

visited array = [true , false , false , false , false]

The graph becomes:

Next, we move to the unvisited nodes of 0. Hence, we move to 2.

We add it to the stack and output array and also mark it as visited.

Stack = [0 , 2]

Output array = [0 , 2]

Visited array = [true , false , true , false , false]

The graph becomes:

Now, we look at the unvisited nodes of 2. We find that these are 1 and 3. We may choose either. Say that we choose 1. So, we add 1 to the stack and output array and mark it as visited.

Stack = [0 , 2 , 1]

Output array = [0 , 2 , 1]

Visited array = [true , true , true , false , false]

The graph becomes:

Next, we have to visit the unvisited nodes adjacent to node 1. We find that these are 3 and 4. We may choose either. Say that we choose 3. Therefore, we add 3 to the stack and output array and also mark it as visited.

Stack = [0 , 2 , 1 , 3]

Output array = [0 , 2 , 1 , 3]

Visited array = [true , true , true , true , false]

The graph becomes:

Now we move on to the unvisited nodes adjacent to 3. However, we find that there are no nodes adjacent to 3 that are unvisited. So, we backtrack to the last node with unvisited adjacent nodes. Hence, we pop 3 from the stack and check unvisited nodes of 1. We find that there is one unvisited node left that is adjacent to one. This node is 4. Therefore, we add it to the stack and output array and also mark it as visited.

Stack = [0 , 2 , 1 , 4]   (3 was removed from the stack)

Output array = [0 , 2 , 1 , 3 , 4]

Visited array = [true , true , true , true , true]

The graph becomes:

Now, we move to the unvisited nodes of 4. We find that no such nodes exist and we must backtrack to the last node with unvisited adjacent nodes. Hence, pop 4 from the stack and move back to 1. We see that no such nodes exist for 1, and pop 1 from the stack as well. Next, we move back to 2 and find that no such nodes exist for 2 also. Finally, we pop 2 from the stack and move on to 0. No such nodes exist for 0 as well. Therefore, zero is also popped from the stack. The stack is now empty and there are no more unvisited nodes. Hence, it can be safely concluded that all the nodes have been visited.

Stack = []

Output array = [0 , 2 , 1 , 3 , 4]

Visited array = [true , true , true , true , true]

Thus, we have successfully implemented Depth First Traversal for a given graph.

The program:

Following is the implementation for Depth First Traversal in python for graphs using adjacency lists:

from collections import defaultdict

d = defaultdict(list)

def addedge(x,y):
    d[x].append(y)

def dfs(d):
    v = len(d)
    visits = [False]*v
    for i in range(v):
        if visits[i] == False:
            dfsRec(i,visits)

def dfsRec(i,visits):
    visits[i] = True
    print(i,"is visited")
    for j in d[i]:
        if visits[j] == False:
            dfsRec(j,visits)

addedge(0, 2) 
addedge(1, 2) 
addedge(1, 3) 
addedge(1, 4) 
addedge(2, 0) 
addedge(2, 1)
addedge(2, 3) 
addedge(3, 1)
addedge(3, 2)
addedge(4, 1)

dfs(d)

The output of the above program is:

Time Complexity of Depth First Traversal:

  • Using adjacency matrix: O(V2)
  • Using adjacency list: O(V+E)

Where V is the number of vertices and E is the number of edges.

The github link for the above program is:

https://github.com/HSNA243/PythonPrograms/blob/master/DFS.py

Visits: 121

3 Replies to “Depth First Traversal”

Leave a Reply

Your email address will not be published. Required fields are marked *