Detect Cycle in an Undirected Graph

Learning to solve competitive questions is the first step to preparing for any technical interview. In this article, let us go through one such important competitive problem statement, which is to check if an undirected graph contains a cycle or not and its most likely to be asked during the technical discussions of product-based companies to test your basic knowledge and understanding of the graphs data structure. But before understanding the problems statement and different approaches to solving it, let us recap the graph data structure in detail below.

What is a Graph?

A graph is a data structure that comprises a restricted set of vertices (or nodes) and edges that connect these vertices. A graph G is an ordered pair G = (V, E), where V is the set of vertices (also called nodes or points) and E is the set of edges in G. In this case, we say that G consists of a set V of vertices and E ⊆ V × V.

Graphs are often used to model relationships between objects. Graphs can be directed or undirected. In an undirected graph, the edges are unordered pairs of vertices, whereas, in a directed graph, the edges have an ordering to them.

For example, suppose we have a social network where people have information about themselves and friends who have similar interests. Each person's profile could be represented as a vertex and each friend as an edge.

Problem Statement

Given a connected undirected graph, check if it contains any cycle or not.

To understand this problem statement, let us first understand the concept of graph data structure.

What is Cycle in Graph?

When it comes to the graph data structure, the path which starts from any given vertex and ends at the same vertex is called the cycle of the graph. Cycle detection is one of the major research areas in today's technological world. Remember that the complexity of detecting a cycle in an undirected graph is omega(n).

The below image shows an example of graph data structure, and we can see that node A-B-D-C-A results as the cycle of the graph.

Now that we have briefly understood graph data structure and cycle, let us learn some simple approaches to detect cycle in undirected graph.

How to Detect Cycle in an Undirect Graph?

Consider the below graph which contains cycle C-D-E-G-F-C

Given a graph and an unvisited node, run a Depth First Search traversal from the unvisited node to detect cycles in the graph. A DFS of a connected graph produces a tree. A graph has a cycle if and only if it contains a back edge. A back edge is an edge joining a node to itself or one of its ancestors in the depth-first search tree produced by the DFS algorithm.

To find the back edge of a node, keep track of nodes that have already been visited. If a back edge to any visited node is encountered, there is a loop and return true.

Sounds confusing?

Let us look at the example below for better understanding:

Example

Consider the below graph to detect cycle in undirected graph using DFS approach. We will also require a parent variable to keep track of the node we are just coming from.

Initially, all the vertex are unvisited and since there is no parent of node A, we assign its parent equal to -1.

Now we start our DFS traversal. Since node A is unvisited, we visit it and its neighbor node are B and C. We go to node B first. Since it’s unvisited, we visit it and also note that the parent variable is now node A as we are coming from node A.

Now for node B, the only neighboring node is A which is visited and also the parent of node B, so we backtrack to node A.

Now from node A, the unvisited neighbor is node C. We visit node C, since we are coming from node A, the parent remains equal to node A.

Now from node C, we have node 3 neighbors. First is node A which is visited but is the parent of node C, and the other is node D and node E which are unvisited. Therefore, we move to node D.

We visit node D and update our parent variable to node C as shown in the below image.

Now from node D, we have node C and node E as neighbors. Here, node C is visited but the parent of node D so we move to the unvisited neighbor of node E. At last, we mark node E as visited. And also note that since we are coming from node D, we update our parent variable to node D.

Now from node E, we have a neighbor i.e., node D which is visited but the parent of node E, and another is node C which is visited but is not a parent of node E.

Since this was the condition we discussed in the above theory, we can say that we have detected a cycle i.e., C-D-E-C. 

Algorithm to detect cycle in undirected graph

Assign the source_vertex to visited
    for all the adjacent_vertices to the source_vertex do
        if the adjacent_vertex is not visited, then
            Assign parent [ adjacent_vertex ] = source_vertex
            detect_cycle (adjacent_vertex)
        else if the parent [ source_vertex ] != adjacent_vertex, then
            cycle detected 
     return

Check out the implementation of the DFS approach to detect cycle in undirected graph using Python programming:

Python Code to detect cycle in an undirected graph

class Graph:
 
    def __init__(self, edges, a):
 
        # Adjacency list representation
        self.adjacencyList = [[] for _ in range(a)]
 
        for (source, destination) in edges:
            self.adjacencyList[source].append(destination)
            self.adjacencyList[destination].append(source)
 
 
# Function for DFS_Traversal traversal
def DFS_Traversal(graph, v, visited, parent_node=-1):
 
    # assign current node as
    visited[v] = True
 
    # loop for every edge (v, u)
    for u in graph.adjacencyList[v]:
 
        # if `u` is not visited
        if not visited[u]:
            if DFS_Traversal(graph, u, visited, v):
                return True
 
        # if `u` is visited, and `u` is not a parent_node
        elif u != parent_node:
            # found a back-edge 
            return True
 
    # No back-edges were found 
    return False
 
 
if __name__ == '__main__':
 
    # List of graph edges
    edges = [
        (0, 1), (0, 2), (2, 3), (2, 4), (3, 4)
    ]
 
    # number of nodes in the graph
    a = 5
 
    # construct graph
    constructed_graph = Graph(edges, a)
 
    # note the visited and unvisited nodes
    visited = [False] * a
 
    # perform DFS traversal from source_node
    if DFS_Traversal(constructed_graph, 0, visited):
        print('Cycle detected')
    else:
        print('Cycle not detected')

Output:

Cycle detected

Time Complexity

The time complexity of using the DFS approach is O(V+E), where V is the number of vertices and E is the number of edges in the given graph.

Conclusion

Competitive problems play an important role in testing any candidate's knowledge during technical interviews. The graph is one such critical data structure to deal with, and therefore, this article explores the problem of detecting cycle in undirected graph using the DFS algorithm. It also represents the respective code of the approach in python programming. To learn more about such technical concepts, visit our blogs by Favtutor.