# 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

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

- 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

- 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

- 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

- 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** :

- 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)
```