**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 is0 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)