Depth First Traversal for a Graph

Depth First Search (BFS) is a recursive graph traversal algorithm that is used to traverse all the vertices of a graph in a depthward motion. In other words, it starts the graph traversal from root node and explores all the branches.

Example of Depth First Traversal for a Graph

Depth First Traversal is used to traverse all the vertices of a graph. Using this algorithm, traversal is done in a depthward motion.

Below is the example of DFS Traversal with input- output constraint and the solution for the example.

Input and Output of the Example

Given the undirected, connected and unweighted graph G, and the task is used to traverse all the vertices of a graph using DFS Traversal starting from 0.

Output:

Depth First Traversal from vertex 0 is 0 1 3 2.

Stepwise Solution of the Depth First Traversal Example

1. Given the undirected, connected and unweighted graph G. Create a set Visited which is used to track on visited vertices and create stack Nxt_Vertex to store next vertices.

2. Start from vertex 0, put the current vertex (0) in Visited list and put all its adjacent vertices ( 1, 3, 2 ) in the stack, left side denotes the top of the stack.

Visited:

0

Nxt_Vertex:

1

3

2

3. Now visit next unvisited vertex from the top of Nxt_Vertex , put the current vertex (1) in Visited list. There is no new vertex.

Visited:

0

1

Nxt_Vertex:

3

2

4. Similarly, visit next unvisited vertex from the top of Nxt_Vertex, put the current vertex (3) in Visited list. There is also no new vertex.

Visited:

0

1

3

Nxt_Vertex:

2

5. Similarly, visit next unvisited vertex from the top of Nxt_Vertex, put the current vertex (2) in Visited list. There is also no new vertex.

Visited:

0

1

3

2

Nxt_Vertex :

6. Since Nxt_Vertex is empty, stop the traversal. Thus the traversal is : 0 1 3 2.

Pseudocode for Depth First Traversal for a Graph

Here’s pseudocode to traverse all the vertices of a graph using DFS Traversal.

Depth_First_Traversal(G, root):

root is visited

for all edges from v to w in G.adjacentEdges(v)  do

if w is not visited then

call Depth_First_Traversal(G, w)

Implementation of Depth First Traversal in Python

def  Depth_First_Traversal(Graph, vertex, visited=None):

if visited is  None:

visited = set()

visited.add(vertex)

print(str(vertex) + " ", end="")

for next_vertex in Graph[vertex] - visited:

if next_vertex not  in visited:

Depth_First_Traversal(Graph, next_vertex, visited)

return visited

if  __name__ == '__main__':

Graph = {0: set([1, 3]), 1: set([3]), 2: set([1]), 3: set([1, 2])}

print("Depth First Traversal: ")

Depth_First_Traversal(Graph, 0)