# Detect Cycle in Undirected Graph using DFS in Python

«
»

This is a Python program to find if an undirected graph contains a cycle using DFS.

Problem Description

The program creates a graph object and allows the user to determine whether the graph contains a cycle.

Problem Solution

1. Create classes for Graph and Vertex.
2. Create a function is_cycle_present_helper that takes a Vertex object v, a set visited and a dictionary parent as arguments.
3. The function works by performing DFS traversal on the graph. If it finds a node that has already been visited, it checks whether the found node is a child of the current node. If not, the graph contains a cycle. The last check is needed because the graph is undirected which means there are two edges between any two adjacent vertices which we do not want to consider as a cycle.
4. The dictionary parent keeps track of the parent of each node in the DFS tree.
5. The function begins by adding v to visited.
6. For each neighbour of v that is not in visited, is_cycle_present_helper is called and its parent is set to v.
7. If is_cycle_present_helper returns True, a cycle is present and True is returned.
8. If a neighbour has already been visited and the parent of v is not that neighbour, a cycle is present and True is returned.
9. After the loop finishes, False is returned to indicate that no cycle is present.
10. Create a function is_cycle_present that takes a Vertex object and a set visited as arguments.
11. It calls is_cycle_present_helper with v, the set visited and a dictionary that maps v to None as the parent parameter. The return value of is_cycle_present_helper is returned.
12. Thus, this function returns True is a cycle is present in the connected component containing v and puts all nodes in the component in set visited.

Program/Source Code

Here is the source code of a Python program to find if an undirected graph contains a cycle using DFS. 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."""

"""Add undirected edge (2 directed edges) between v1_key and v2_key with
given weight."""

def does_undirected_edge_exist(self, v1_key, v2_key):
"""Return True if there is an undirected edge between v1_key and v2_key."""
return (self.does_edge_exist(v1_key, v2_key)
and self.does_edge_exist(v1_key, v2_key))

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 is_cycle_present(v, visited):
"""Return True if cycle is present in component containing vertex and put
all vertices in component in set visited."""
parent = {v: None}
return is_cycle_present_helper(v, visited, parent)

def is_cycle_present_helper(v, visited, parent):
"""Return True if cycle is present in component containing vertex and put
all vertices in component in set visited. Uses dictionary parent to keep
track of parents of nodes in the DFS tree."""
for dest in v.get_neighbours():
if dest not in visited:
parent[dest] = v
if is_cycle_present_helper(dest, visited, parent):
return True
else:
if parent[v] is not dest:
return True
return False

g = Graph()
print('Undirected Graph')
print('cycle')
print('display')
print('quit')

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

operation = do
suboperation = do
if suboperation == 'vertex':
key = int(do)
if key not in g:
else:
elif suboperation == 'edge':
v1 = int(do)
v2 = int(do)
if v1 not in g:
print('Vertex {} does not exist.'.format(v1))
elif v2 not in g:
print('Vertex {} does not exist.'.format(v2))
else:
if not g.does_undirected_edge_exist(v1, v2):
else:

elif operation == 'cycle':
present = False
visited = set()
for v in g:
if v not in visited:
if is_cycle_present(v, visited):
present = True
break

if present:
print('Cycle present.')
else:
print('Cycle not present.')

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 determine whether the graph contains a cycle, is_cycle_present is called with a vertex from the graph and an empty set visited.
4. If is_cycle_present returns True, a cycle is present. Otherwise, if not all vertices were visited, is_cycle_present is called again with an unvisited source vertex.
5. This continues until all vertices have been visited or is_cycle_present returns True.
6. If all vertices have been visited, then there are no cycles in the graph.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Runtime Test Cases
```Case 1:
Undirected Graph
cycle
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 edge 1 2
What would you like to do? cycle
Cycle not present.
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 vertex 5
What would you like to do? add edge 4 5
What would you like to do? add edge 5 3
What would you like to do? cycle
Cycle present.
What would you like to do? quit

Case 2:
Undirected Graph
cycle
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? cycle
Cycle not present.
What would you like to do? add edge 1 2
What would you like to do? add vertex 3
What would you like to do? add edge 2 3
What would you like to do? cycle
Cycle not present.
What would you like to do? add edge 3 1
What would you like to do? cycle
Cycle present.
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. 