Given an undirected graph containing ‘n’ nodes and ‘e’ edges. Determine whether or not the graph contains a cycle.
Takeaways
Worst-case time complexity of Depth first search for detecting the cycle in undirected graph is O(n) where n is the number of nodes.
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:
YES
If the graph is cyclic.
NO
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++:
//Detect cycle in undirected graph
#include "bits/stdc++.h"
using namespace std;
/*Utility function
nd -> current node
par -> parent node of cur
vis -> visited array
parents -> parent nodes array
*/
bool dfs(const int& nd, int par, vector<bool>& vis, vector<int>& parents, const vector<vector<int>>& g) {
//Mark current node as visited
vis[nd] = true;
for (const int& u : g[nd]) {
//If u is parent of cur, then just ignore it
if (u == par)
continue;
//If u is visited, means a cycle has been caught
if (vis[u])
return true;
//Mark nd as parent to u
parents[u] = nd;
if (dfs(u, parents[u], vis, parents, g))
return true;
}
return false;
}
bool isCyclic(const vector<vector<int>>& graph) {
//sz -> number of nodes
int sz = graph.size();
vector<bool>vis(sz, false);
vector<int>parents(sz, -1);
for (int i = 0; i < sz; i++)
if (!vis[i] && dfs(i, parents[i], vis, parents, graph))
return true;
return false;
}
int main() {
int n, e;
cin >> n >> e;
vector<vector<int>>graph(n, vector<int>());
for (int i = 0;i < e;++i) {
int u, v;
cin >> u >> v;
if (u == v) {
cout << "YES" << endl;
return 0;
}
graph[u].push_back(v);
graph[v].push_back(u);
}
cout << (isCyclic(graph) ? "YES" : "NO") << endl;
return 0;
}
2. Java:
//Detect cycle in undirected graph
import java.util.*;
class Main {
/*
* Utility function
* nd -> current node
* par -> parent node of cur
* vis -> visited array
* parents -> parent nodes array
*/
private static boolean dfs(int nd, int par, ArrayList<Boolean> vis, ArrayList<Integer> parents, ArrayList<ArrayList<Integer>> g) {
// Mark current node as visited
vis.set(nd, true);
for (int i = 0; i < g.get(nd).size(); ++i) {
int u = g.get(nd).get(i);
// If u is parent of cur, then just ignore it
if (u == par)
continue;
// If u is visited, means a cycle has been caught
if (vis.get(u) == true)
return true;
// Mark nd as parent to u
parents.set(u, nd);
if (dfs(u, parents.get(u), vis, parents, g))
return true;
}
return false;
}
static private boolean isCyclic(ArrayList<ArrayList<Integer>> graph) {
// sz -> number of nodes
int sz = graph.size();
ArrayList<Boolean> vis = new ArrayList<Boolean>(sz);
ArrayList<Integer> parents = new ArrayList<Integer>(sz);
for (int i = 0; i < sz; i++) {
vis.add(false);
parents.add(-1);
}
for (int i = 0; i < sz; i++)
if (vis.get(i) == false && dfs(i, parents.get(i), vis, parents, graph))
return true;
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n, e;
n = scan.nextInt();
e = scan.nextInt();
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < n; i++)
graph.add(new ArrayList<Integer>());
for (int i = 0; i < e; ++i) {
int u, v;
u = scan.nextInt();
v = scan.nextInt();
if (u == v) {
System.out.println("YES");
scan.close();
return;
}
graph.get(u).add(v);
graph.get(v).add(u);
}
scan.close();
System.out.println(isCyclic(graph) == true ? "YES" : "NO");
}
}
3. Python:
# Detect cycle in undirected graph
from collections import defaultdict
from os import kill
# graph class
class graph:
def __init__(self, nodes):
# Number of nodes
self.v = nodes
self.graph = defaultdict(list)
# Addition of an edge to the graph
def addEdge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# v -> current node
# visited -> array to keep track of visited nodes
# parent -> parent of current node
def dfs(self, v, visited, parent):
# Mark v as visited
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
if(self.dfs(i, visited, v)):
return True
# If the node i is parent to v, then just ignore it
elif parent != i:
return True
return False
def isCyclic(self):
visited = [False]*(self.v)
for i in range(self.v):
if visited[i] == False:
if(self.dfs(i, visited, -1)) == True:
return True
return False
n = int(input())
g = graph(n)
e = int(input())
fl = False
for i in range(e):
u, v = map(int, input().split())
if u == v:
fl = True
break
g.addEdge(u, v)
if fl or g.isCyclic():
print("YES")
else:
print("NO")
Input:
4
4
0 1
1 2
2 3
2 0
Output:
YES
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++
#include <bits/stdc++.h>
using namespace std;
// g -> graph matrix
// nd -> current node
// vis -> visited nodes array
bool bfs(const vector<vector<int>>& g, int nd, vector<bool>& vis) {
// Number of nodes
int sz = g.size();
// parents -> parent of each node
vector<int> parents(sz, -1);
queue<int> q;
// Mark cur as visited
vis[nd] = true;
q.push(nd);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
parents[v] = u;
continue;
}
// Check if v is parent of u
if (parents[u] != v)
return true;
}
}
return false;
}
bool isCyclic(const vector<vector<int>>& graph) {
int sz = graph.size();
vector<bool> vis(sz, false);
for (int i = 0; i < sz; i++)
if (!vis[i] && bfs(graph, i, vis))
return true;
return false;
}
int main() {
int n, e;
cin >> n >> e;
vector<vector<int>>graph(n);
for (int i = 0;i < e;++i) {
int u, v;
cin >> u >> v;
if (u == v) {
cout << "YES" << endl;
return 0;
}
graph[u].push_back(v);
graph[v].push_back(u);
}
cout << (isCyclic(graph) ? "YES" : "NO") << endl;
return 0;
}
2. Java
import java.util.*;
class Main {
// g -> graph matrix
// nd -> current node
// vis -> visited nodes array
private static boolean bfs(ArrayList<ArrayList<Integer>> g, int nd, ArrayList<Boolean> vis) {
// Number of nodes
int sz = g.size();
// parents -> parent of each node
ArrayList<Integer> parents = new ArrayList<Integer>();
for (int i = 0; i < sz; i++)
parents.add(-1);
Queue<Integer> q = new LinkedList<Integer>();
// Mark cur as visited
vis.set(nd, true);
q.add(nd);
while (!q.isEmpty()) {
int u = q.remove();
for (int V = 0; V < g.get(u).size(); ++V) {
int v = g.get(u).get(V);
if (vis.get(v) == false) {
vis.set(v, true);
q.add(v);
parents.set(v, u);
continue;
}
// Check if v is parent of u
if (parents.get(u) != v)
return true;
}
}
return false;
}
private static boolean isCyclic(ArrayList<ArrayList<Integer>> graph) {
int sz = graph.size();
ArrayList<Boolean> vis = new ArrayList<Boolean>();
for (int i = 0; i < sz; i++)
vis.add(false);
for (int i = 0; i < sz; i++)
if (vis.get(i) == false && bfs(graph, i, vis))
return true;
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n, e;
n = scan.nextInt();
e = scan.nextInt();
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < n; i++)
graph.add(new ArrayList<Integer>());
for (int i = 0; i < e; ++i) {
int u, v;
u = scan.nextInt();
v = scan.nextInt();
if (u == v) {
System.out.println("YES");
scan.close();
return;
}
graph.get(u).add(v);
graph.get(v).add(u);
}
scan.close();
System.out.println(isCyclic(graph) == true ? "YES" : "NO");
}
}
3. Python
from collections import deque
# Adding an edge to the graph
def addEdge(g, u, v):
g[u].append(v)
g[v].append(u)
def bfs(graph, nd, sz, visited):
parent = [-1] * sz
q = deque()
visited[nd] = True
q.append(nd)
while q:
u = q.pop()
for v in graph[u]:
if not visited[v]:
visited[v] = True
q.append(v)
parent[v] = u
continue
if parent[u] != v:
return True
return False
def isCyclic(graph, sz):
visited = [False] * sz
for i in range(sz):
if not visited[i] and bfs(graph, i, sz, visited):
return True
return False
n = int(input())
e = int(input())
if e == 0:
print("NO")
exit()
graph = [[] for i in range(n)]
for i in range(e):
u, v = map(int, input().split())
addEdge(graph, u, v)
if isCyclic(graph, n):
print("Yes")
else:
print("No")
Input:
4
4
0 1
1 2
2 3
2 0
Output:
YES
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.
Conclusion
- An undirected graph is a set of nodes and edges, such that an edge signifies bidirectionality.
- 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.
- We can solve the problem of detecting a cycle in an undirected graph by using dfs or bfs.
