 # 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.

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.

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.

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.

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(), 2: set(), 3: set([1, 2])}

print("Depth First Traversal: ")

Depth_First_Traversal(Graph, 0)```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.