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

This is a Python program to implement Depth-First Search on a graph using recursion.

Problem Description

The program creates a graph object and allows the user to perform DFS traversal on it.

Problem Solution

1. Create classes for Graph and Vertex.
2. Create a function display_dfs_helper that takes a Vertex object v and a set visited as arguments.
3. The function begins by adding v to visited and displaying v.
4. For each neighbour of v that is not in visited, display_dfs_helper is called on the neighbour.
5. Create a function display_dfs that takes a Vertex object v as argument.
6. It calls display_dfs_helper with v and an empty set for the set visited.
7. This algorithm also works for undirected graphs. In an undirected graph, whenever edge (u, v) is added to the graph, the reverse edge (v, u) is also added.

Program/Source Code

Here is the source code of a Python program to implement DFS traversal on a graph using recursion. The program output is shown below.

```class Graph:
def __init__(self):
# dictionary containing keys that map to the corresponding vertex object
self.vertices = {}

"""Add a vertex with the given key to the graph."""
vertex = Vertex(key)
self.vertices[key] = vertex

def get_vertex(self, key):
"""Return vertex object with the corresponding key."""
return self.vertices[key]

def __contains__(self, key):
return key in self.vertices

"""Add edge from src_key to dest_key with given weight."""

def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from src_key to dest_key."""
return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __iter__(self):
return iter(self.vertices.values())

class Vertex:
def __init__(self, key):
self.key = key
self.points_to = {}

def get_key(self):
"""Return key corresponding to this vertex object."""
return self.key

"""Make this vertex point to dest with given edge weight."""
self.points_to[dest] = weight

def get_neighbours(self):
"""Return all vertices pointed to by this vertex."""
return self.points_to.keys()

def get_weight(self, dest):
"""Get weight of edge from this vertex to dest."""
return self.points_to[dest]

def does_it_point_to(self, dest):
"""Return True if this vertex points to dest."""
return dest in self.points_to

def display_dfs(v):
"""Display DFS traversal starting at vertex v."""
display_dfs_helper(v, set())

def display_dfs_helper(v, visited):
"""Display DFS traversal starting at vertex v. Uses set visited to keep
print(v.get_key(), end=' ')
for dest in v.get_neighbours():
if dest not in visited:
display_dfs_helper(dest, visited)

g = Graph()
print('dfs <vertex key>')
print('display')
print('quit')

while True:
do = input('What would you like to do? ').split()

operation = do[0]
suboperation = do[1]
if suboperation == 'vertex':
key = int(do[2])
if key not in g:
else:
elif suboperation == 'edge':
src = int(do[2])
dest = int(do[3])
if src not in g:
print('Vertex {} does not exist.'.format(src))
elif dest not in g:
print('Vertex {} does not exist.'.format(dest))
else:
if not g.does_edge_exist(src, dest):
else:

elif operation == 'dfs':
key = int(do[1])
print('Depth-first Traversal: ', end='')
vertex = g.get_vertex(key)
display_dfs(vertex)
print()

elif operation == 'display':
print('Vertices: ', end='')
for v in g:
print(v.get_key(), end=' ')
print()

print('Edges: ')
for v in g:
for dest in v.get_neighbours():
w = v.get_weight(dest)
print('(src={}, dest={}, weight={}) '.format(v.get_key(),
dest.get_key(), w))
print()

elif operation == 'quit':
break```
Program Explanation

1. An instance of Graph is created.
2. A menu is presented to the user to perform various operations on the graph.
3. To perform DFS traversal starting at some vertex, display_dfs is called.

Runtime Test Cases
```Case 1:
dfs <vertex key>
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add vertex 4
What would you like to do? add vertex 5
What would you like to do? add vertex 6
What would you like to do? add vertex 7
What would you like to do? add edge 1 2
What would you like to do? add edge 2 3
What would you like to do? add edge 3 4
What would you like to do? add edge 3 5
What would you like to do? add edge 1 6
What would you like to do? add edge 6 2
What would you like to do? dfs 1
Depth-first Traversal: 1 6 2 3 4 5
What would you like to do? quit

Case 2:
dfs <vertex key>
display
quit
What would you like to do? add vertex 1
What would you like to do? dfs 1
Depth-first Traversal: 1
What would you like to do? add vertex 2
What would you like to do? add edge 1 2
What would you like to do? dfs 1
Depth-first Traversal: 1 2
What would you like to do? dfs 2
Depth-first Traversal: 2
What would you like to do? add edge 2 1
What would you like to do? add vertex 3
What would you like to do? add vertex 4
What would you like to do? add edge 2 3
What would you like to do? add edge 2 4
What would you like to do? dfs 1
Depth-first Traversal: 1 2 3 4
What would you like to do? dfs 2
Depth-first Traversal: 2 3 4 1
What would you like to do? quit```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]