Detect Cycle in Undirected Graph

Example of problem.

Consider the following image.

It shows an undirected graph with a cycle. Now have a look at the following image.

It shows an undirected graph without any cycle

Explanation of the problem.

We have to detect cycle in undirected graph. In a graph, any path with 1 or more duplicates of any node(s) present in the path is known as a cycle A graph containing a cycle is called cyclic. For example, an edge from a node itself is a cycle. It is a trivial case often referred to as a “self-loop”. A path that ends at the same node that it begins from also forms a cycle.

Constraints for the problem

The input will be as follows: The first line contains an integer ‘n’, the number of nodes numbered from 1 to n. 1 <= n <= 10^5 The next line contains another integer ‘e’, the number of edges. The next e lines contain space isolated integers ‘u’ and ‘v’, which represent an edge between nodes numbered u and v respectively. The output must be of the form:

If the graph is cyclic.

Otherwise.

First approach: Depth First Traversal

We use depth-first search (D.F.S.) to construct a solution for this problem. We run a sequence of DFS in the graph. Initially, nodes are labeled 0 (zero) which implies the node is unvisited. From each unvisited node, begin the DFS, label the node visited with 1 while entering, and label it 2 on exit.

If DFS moves to a node labeled 1, then we have discovered a cycle. It is to be noted that since the graph is undirected, the edge from a node to its parent must not be considered. The cycle can itself be reconstructed using the parent array. Implementation:

1. C++:

2. Java:

3. Python:

Input:

Output:

Analysis of time complexity

The worst-case time complexity of this algorithm is O(e) where e is the number of edges.

HOW?

We perform a basic depth-first search in this algorithm, which at most will run all the edges. There will not be repetitive recursions (for the same edges) because we keep track of visited edges.

Analysis of space complexity

The worst-case time complexity of this algorithm is O(n) where n is the number of nodes.

HOW?

We make only 2 arrays of size n.

Second approach: Breadth-first search

The logic used in this second approach to detect cycle in undirected graph is quite similar to the one used in the previous (dfs) approach. But this (bfs) approach differs from it in that we use bfs in place of dfs for exploring the graph. Implementation:

1. C++

2. Java

3. Python

Input:

Output:

Analysis of time complexity

The worst-case time complexity of this algorithm is O(e) where e is the number of edges.

HOW?

We perform a basic breadth-first search in this algorithm, which at most will run all the edges. There will not be repetitive entries of nodes in the queue (for the same edges) because we keep track of visited edges.

Analysis of space complexity

The worst-case time complexity of this algorithm is O(n) where n is the number of nodes.

HOW?

We make only 2 arrays of size n.