Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Graph?
3.
What is Cycle in Graph?
4.
What is Detect cycle in an Undirected graph?
5.
Find cycle in undirected Graph using DFS
5.1.
Algorithm for the solution
5.2.
Implementation of the solution
5.3.
C++
5.4.
Java
5.5.
Python
5.6.
Javascript
5.7.
C#
6.
Frequently Asked Questions
6.1.
How do you determine if an undirected graph has a cycle?
6.2.
Can BFS be used to find cycles in undirected graphs?
6.3.
How can we detect a cycle in undirected graph?
6.4.
How to detect cycle in an undirected graph adjacency list?
6.5.
What is undirected cyclic graph?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Detect Cycle in Undirected Graph

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this blog, we will be discussing a method to detect cycles in undirected graph. Before diving into the solution, let's again look at what exactly is an undirected graph and a cycle in it.

Detect Cycle in Undirected Graph

A graph whose edges have no preference for the direction of data flowing through them is called an undirected graph, and a cycle in a graph is a non-empty trail with repeated first and last vertices.

Detect Cycle in Undirected Graph Using DFS

For example, in the above figure, the graph on the right contains a cycle.

What is a Graph?

According to Wikipedia, in mathematics, a graph is a visual representation or diagram that shows facts or values in an ordered way.
The relationships between two or more items are frequently represented by the points on a graph. When discussing data structures and algorithms,  a graph is a non-linear data structure made up of vertices and edges. In a graph, the edges are the lines or arcs that link any two nodes, while the vertices are occasionally also referred to as nodes. A graph is more strictly made up of a collection of vertices (V) and a set of edges ( E ). The graph is denoted by the expression: G(E, V).

Check also: Application of graph data structure

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

What is Cycle in Graph?

A cycle in graph theory is a path that originates at one vertex and terminates at the same vertex.

A significant field of computer science research is cycle detection. Finding a cycle in an undirected graph is extremely difficult. It's complexity is Omega(n).

Let us understand this concept with an example. 

Cycle in Graph

In this example, there is a cycle between the nodes 4 - 3 -6 - 4. These nodes are forming a cycle. 

What is Detect cycle in an Undirected graph?

In this section of the blog, we will see how to detect cycle in any undirected graph. For this we are going to use DFS algorithm to find cycle in any undirected graph. Vertices are added to a stack by DFS. We begin by pushing some vertex v n onto the stack. Then:

  1. If v n has any unvisited neighbours, we put one of them, v n', into the stack and then repeat this process, making v n' now v n.
  2. After v n has visited all of its neighbours, we remove it from the stack and go back to step 1.

Now, we may slightly modify DFS's logic in order to detect a cycle: If a neighbour of v n's has recently visited, then:
either it is the same as v n or it is not the same as v_n's parent. And a cycle begins. We will see this in detail in the later part of this blog. 

Find cycle in undirected Graph using DFS

This approach is very similar to the method for detecting cycles in directed graph. In this method also, we use DFS Algorithm to detect cycles in an undirected graph as the DFS of a graph will produce a DFS tree, which is a reordered representation of the edges and vertices of the graph. In this DFS tree, we have to find a back edge, an edge either connecting a vertex to itself or its ancestor. If we find such an edge, we will conclude that the graph is cyclic.

Find cycle in undirected Graph using DFS

In the above diagram, let us say we start DFS from node 2 and we visit the nodes: 0, 1, 3, 4 and 5 through the edges: 2->0, 0->1, 1->3, 3->4 and 4->5. These edges become the forward edges in our DFS traversal of the graph which eventually form a DFS tree considering the forward edges only whereas the edges which were not the part of our DFS i.e 0->3 and 3->5 become the back edges.

We will be using an array of visited vertices during the DFS traversal to check for back edges, so whenever we find an edge that goes back to a vertex already in the visited array, we return true as a result that the graph contains a cycle.

Algorithm for the solution

  1. Take the number of edges and vertices as user input.
  2. Use vertex visited array and parent node to create a recursive function. 
  3. Mark the current vertex as visited. 
  4. Make recursive calls for all the unvisited adjacent vertices for the current vertex, and if any of these recursive functions return true, return true as the final answer.
  5. If any adjacent vertex is already in the visited array, mark the answer as true.
  6. Return false if none of the above steps returns true. 

Implementation of the solution

  • C++
  • Java
  • Python
  • Javascript
  • C#

C++

#include<bits/stdc++.h>
using namespace std;
//Class for the graph.
class graph
{
int v;
//Adjacency list.
list<int> *adjacencylist;
//Function to detectcycle.
bool checkcycle2(int v, bool vertvisited[], int parentnode);
public:
graph(int v);
void drawedge(int v, int u);
bool checkcycle();
};
//Constructor for a graph with v nodes.
graph::graph(int v)
{
this->v=v;
adjacencylist= new list<int>[v];
}
//To add edges in the graph.
void graph::drawedge(int v, int u)
{
adjacencylist[v].push_back(u);
adjacencylist[u].push_back(v);
}
//Function to keep track of visited nodes.
bool graph::checkcycle2(int v, bool vertvisited[], int parentnode)
{
//Marking the vertex as visited.
vertvisited[v]=true;
//Making recursive calls for the adjacent
//vertices and return true if any back edge is
//found.
list<int>::iterator itr;
for(itr=adjacencylist[v].begin();itr!=adjacencylist[v].end();++itr)
{
if (!vertvisited[*itr])
{
if(checkcycle2(*itr, vertvisited, v))
{
return true;
}
}
else if (*itr != parentnode)
{
return true;
}
}
return false;
}
bool graph::checkcycle()
{
//Declare and initialise the visited and recursion stack array as false.
bool *vertvisited=new bool[v];
for(int i=0;i<v;i++)
{
vertvisited[i]=false;
}
//Call the "checkcycle2" function for cycle
//detection.
for(int i=0;i<v;i++)
{
if(!vertvisited[i])
{
if(checkcycle2(i, vertvisited, -1))
{
return true;
}
}
}
return false;
}
//Driver function.
int main()
{
graph g(6);
g.drawedge(0, 1);
g.drawedge(1, 5);
g.drawedge(5, 4);
g.drawedge(4, 0);
g.drawedge(4, 3);
g.drawedge(3, 2);
g.drawedge(0, 2);
//Function call and print the result.
if(g.checkcycle())
cout << "Graph is cyclic";
else
cout << "Graph is acyclic";
return 0;
}

Java

import java.util.*;

class Graph {
private int v;
private LinkedList<Integer>[] adjacencyList;

public Graph(int v) {
this.v = v;
adjacencyList = new LinkedList[v];
for (int i = 0; i < v; i++) {
adjacencyList[i] = new LinkedList<>();
}
}

public void addEdge(int v, int u) {
adjacencyList[v].add(u);
adjacencyList[u].add(v);
}

private boolean isCyclicUtil(int v, boolean[] visited, int parent) {
visited[v] = true;
for (int neighbor : adjacencyList[v]) {
if (!visited[neighbor]) {
if (isCyclicUtil(neighbor, visited, v)) {
return true;
}
} else if (neighbor != parent) {
return true;
}
}
return false;
}

public boolean isCyclic() {
boolean[] visited = new boolean[v];
for (int i = 0; i < v; i++) {
if (!visited[i] && isCyclicUtil(i, visited, -1)) {
return true;
}
}
return false;
}

public static void main(String[] args) {
Graph g = new Graph(6);
g.addEdge(0, 1);
g.addEdge(1, 5);
g.addEdge(5, 4);
g.addEdge(4, 0);
g.addEdge(4, 3);
g.addEdge(3, 2);
g.addEdge(0, 2);

if (g.isCyclic()) {
System.out.println("Graph is cyclic");
} else {
System.out.println("Graph is acyclic");
}
}
}

Python

from collections import defaultdict

class Graph:
def __init__(self, v):
self.v = v
self.adjacency_list = defaultdict(list)

def add_edge(self, v, u):
self.adjacency_list[v].append(u)
self.adjacency_list[u].append(v)

def is_cyclic_util(self, v, visited, parent):
visited[v] = True
for neighbor in self.adjacency_list[v]:
if not visited[neighbor]:
if self.is_cyclic_util(neighbor, visited, v):
return True
elif neighbor != parent:
return True
return False

def is_cyclic(self):
visited = [False] * self.v
for i in range(self.v):
if not visited[i] and self.is_cyclic_util(i, visited, -1):
return True
return False

# Driver code
g = Graph(6)
g.add_edge(0, 1)
g.add_edge(1, 5)
g.add_edge(5, 4)
g.add_edge(4, 0)
g.add_edge(4, 3)
g.add_edge(3, 2)
g.add_edge(0, 2)

if g.is_cyclic():
print("Graph is cyclic")
else:
print("Graph is acyclic")

Javascript

class Graph {
constructor(v) {
this.v = v;
this.adjacencyList = new Array(v).fill([]).map(() => []);
}

addEdge(v, u) {
this.adjacencyList[v].push(u);
this.adjacencyList[u].push(v);
}

isCyclicUtil(v, visited, parent) {
visited[v] = true;
for (const neighbor of this.adjacencyList[v]) {
if (!visited[neighbor]) {
if (this.isCyclicUtil(neighbor, visited, v)) {
return true;
}
} else if (neighbor !== parent) {
return true;
}
}
return false;
}

isCyclic() {
const visited = new Array(this.v).fill(false);
for (let i = 0; i < this.v; i++) {
if (!visited[i] && this.isCyclicUtil(i, visited, -1)) {
return true;
}
}
return false;
}
}

// Driver code
const g = new Graph(6);
g.addEdge(0, 1);
g.addEdge(1, 5);
g.addEdge(5, 4);
g.addEdge(4, 0);
g.addEdge(4, 3);
g.addEdge(3, 2);
g.addEdge(0, 2);

if (g.isCyclic()) {
console.log("Graph is cyclic");
} else {
console.log("Graph is acyclic");
}

C#

using System;
using System.Collections.Generic;

class Graph
{
private int v;
private List<int>[] adjacencyList;

public Graph(int v)
{
this.v = v;
adjacencyList = new List<int>[v];
for (int i = 0; i < v; i++)
{
adjacencyList[i] = new List<int>();
}
}

public void AddEdge(int v, int u)
{
adjacencyList[v].Add(u);
adjacencyList[u].Add(v);
}

private bool CheckCycleUtil(int v, bool[] vertVisited, int parentNode)
{
vertVisited[v] = true;
foreach (int neighbor in adjacencyList[v])
{
if (!vertVisited[neighbor])
{
if (CheckCycleUtil(neighbor, vertVisited, v))
{
return true;
}
}
else if (neighbor != parentNode)
{
return true;
}
}
return false;
}

public bool CheckCycle()
{
bool[] vertVisited = new bool[v];
for (int i = 0; i < v; i++)
{
vertVisited[i] = false;
}

for (int i = 0; i < v; i++)
{
if (!vertVisited[i])
{
if (CheckCycleUtil(i, vertVisited, -1))
{
return true;
}
}
}
return false;
}

// Driver function.
static void Main()
{
Graph g = new Graph(6);
g.AddEdge(0, 1);
g.AddEdge(1, 5);
g.AddEdge(5, 4);
g.AddEdge(4, 0);
g.AddEdge(4, 3);
g.AddEdge(3, 2);
g.AddEdge(0, 2);

// Function call and print the result.
if (g.CheckCycle())
{
Console.WriteLine("Graph is cyclic");
}
else
{
Console.WriteLine("Graph is acyclic");
}
}
}

Output-

Graph is cyclic

 

The time complexity of the above approach to detect cycles in a directed graph is O(V+E), where V is the number of vertices in the graph and E is the number of edges. This happens because we are doing the DFS of the tree, which has the same time complexity.

The space complexity of the above approach is O(V).

You can also read Detect cycle in an undirected graph here.

Frequently Asked Questions

How do you determine if an undirected graph has a cycle?

If an undirected graph has a back edge in its DFS tree, we can conclude that it contains a cycle. Or it can be said that A cycle in graph theory is a path that originates at one vertex and terminates at the same vertex.

Can BFS be used to find cycles in undirected graphs?

Because you can go back further with depth first search than breadth first search, it uses less memory. Using the call stack makes it simpler to implement, but this depends on the longest path not filling the stack to the brim.

How can we detect a cycle in undirected graph?

We will apply the DFS traversal for the specified graph to determine whether or not there are cycles in the undirected graph. When we discover any nearby vertex u, such that u has already been visited and u is not the parent of vertex v, we know that vertex v has been visited. One cycle is then found.

How to detect cycle in an undirected graph adjacency list?

Use depth-first search (DFS) to traverse the graph. If you encounter an already visited node, and it is not the parent, a cycle exists.

What is undirected cyclic graph?

An undirected cyclic graph is a graph without a designated direction in edges where a cycle, a closed path of edges, exists.

Conclusion

In this blog, we learned to detect cycles in undirected graph.

To detect the cycles in an undirected graph, we started with a Depth-first search traversal of the graph. We maintain an array of all the visited vertices, and during the traversal, whenever we get an edge that goes back to an already visited vertex, also known as a back edge. We return the answer that the graph is cyclic.
Check out this problem - No of Spanning Trees in a Graph

You must check out the blog on the detecting cycle in a directed graph as well. You can practice similar problems on Coding Ninjas Studio as well.

Live masterclass