Learn Programming and technology with ease @ developerpublish.com

HomePythonPython Program to Implement Depth First Search on a Graph using Recursion

# Python Program to Implement Depth First Search on a Graph using Recursion

This Python program implements Depth-First Search (DFS) on a graph using recursion. DFS explores as far as possible along each branch before backtracking.

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along a branch before backtracking. Itâ€™s often implemented using recursion or a stack data structure. DFS is used to explore and analyze graphs, find connected components, solve puzzles, and more. In this introduction, Iâ€™ll provide an overview of how to implement DFS on a graph using recursion.

## Problem Statement

You are given a graph represented as an adjacency list. Implement the Depth First Search (DFS) algorithm using recursion to traverse the graph, starting from a given source vertex. Your task is to print the vertices in the order they are visited during the DFS traversal.

## Python Program to Implement Depth First Search on a Graph using Recursion

```class Graph:
def __init__(self):
self.graph = {}

if vertex in self.graph:
self.graph[vertex].append(edge)
else:
self.graph[vertex] = [edge]

def dfs_recursive(self, start_vertex, visited=None):
if visited is None:
visited = set()

if start_vertex not in visited:
print(start_vertex)

if start_vertex in self.graph:
for neighbor in self.graph[start_vertex]:
self.dfs_recursive(neighbor, visited)

# Create a graph and add edges
g = Graph()

# Perform DFS starting from vertex 'A'
print("DFS starting from vertex 'A':")
g.dfs_recursive('A')
```

## How it Works

1. Initialization:
• Create an empty set or list to keep track of visited vertices. Weâ€™ll use a set called `visited`.
2. Starting Vertex:
• Begin the DFS traversal from the given source vertex. Mark this vertex as visited by adding it to the `visited` set.
3. Recursive Exploration:
• For the current vertex, explore all of its unvisited neighboring vertices.
• For each unvisited neighbor:
• Mark the neighbor as visited by adding it to the `visited` set.
• Recursively apply the DFS algorithm to the unvisited neighbor. This step effectively explores deeper into the graph along the current branch.
• Repeat this process for all unvisited neighbors of the current vertex.
4. Backtracking:
• When there are no unvisited neighbors left for the current vertex, return from the recursion. This represents backtracking to the previous level in the graph traversal.
• Continue this process until you have visited all reachable vertices from the source vertex.
5. Result:
• During the DFS traversal, the algorithm will print the vertices in the order they are visited. This order forms a depth-first traversal of the graph, where you explore as far as possible along one branch before backtracking.

## Input/ Output

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve the Celebrity Problem

This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...

#### Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...