Detecting cycle in an undirected graphs using Depth-First-Search (DFS)
- Cycle in undirected graphs can be detected easily using a depth-first search traversal.
- Idea
While doing a depth-first search traversal, we keep track of the visited node’s parent along with the list of visited nodes. During the traversal, if an adjacent node is found visited that is not the parent of the source node, then we have found a cycle in the current path.
Consider the below undirected graph with 4 nodes [ 0, 1, 2 and 3 ] as show in example below. This undirected graph has a cycle [ 0 -> 1 -> 2 -> 3 -> 0 ].
The idea is a follows, We start with node 0, mark 0 as visited and visit its adjacent nodes i.e 1. Parent of 1 gets stored as 0. We then go to node 1, mark 1 as visited and visit its adjacent nodes i.e 2. Thus parent of 2 gets stored as 1. We then go to node 2, mark 2 as visited and visit its adjacent nodes i.e 3. Thus parent of 3 gets stored as 2. We then go to node 3, mark 3 as visited and visit its adjacent nodes i.e 0. But since 0 was marked visited and 0 is also not the parent of node 3, means that there was a cycle in the graph.
Example
Algorithm : Detect_Cycle ( Node source_node )
1. Mark the source_node as visited. 2. For all the adjacent nodes to the source_node do 3. If the adjacent_node has not been visited, then 4. Set parent [ adjacent_node ] = source_node. 5. Detect_Cycle (adjacent_node) 6. Else If the parent [ source_node ] != adjacent_node, then 7. Cycle found. Return.
Time complexity : O ( E + V ). This algorithm uses a depth-first search traversal for traversing all the nodes in the graph. As the graph is stored in an adjacency list, the neighbors of a vertex on the outgoing edge are explored successively/linearly. As each vertex is explored only once, all the vertices are explored in O ( V ) time. The total number of edges ( maintained in the adjacency list ) are 2*E for an undirected graph. Thus the time complexity is O ( 2.E + V ) for a directed graph.
Program for detecting cycle in an undirected graph
from collections import defaultdict
class Graph:
def __init__(self, nodes : int):
# The default dictionary would create an empty list as a default (value)
# for the nonexistent keys.
self.adjlist = defaultdict(list)
self.nodes = nodes
self.visited = [False] * nodes
# parent stores the parent node of the visited node, this is used
# for finding cycle in an un-directed graph.
self.parent= [None] * nodes
self.cycle_present = False
def AddEdge (self, src : int, dst : int, bidirectional : bool):
self.adjlist[src].append(dst)
if bidirectional == True:
self.adjlist[dst].append(src)
# Function detects cycle in an undirected graph
# using DFS technique at its core
def DetectCycle (self, src : int):
self.visited[src] = True
for adj_node in self.adjlist[src]:
if self.visited[adj_node] == False:
self.parent[adj_node] = src
self.DetectCycle (adj_node)
elif self.parent[src] != adj_node:
self.cycle_present = True
return
def CyclePresent(self):
return self.cycle_present
def main():
nodes = 7
g1_undirected = Graph(nodes)
# Undirected graph 1
# 0
# / \
# 1 2
# / \
# 3 4
# / \
# 5 6 */
g1_undirected.AddEdge(0, 1, True)
g1_undirected.AddEdge(0, 2, True)
g1_undirected.AddEdge(2, 3, True)
g1_undirected.AddEdge(2, 4, True)
g1_undirected.AddEdge(4, 5, True)
g1_undirected.AddEdge(4, 6, True)
g1_undirected.DetectCycle(0)
if g1_undirected.CyclePresent() == True:
print("Cycle found in the undirected graph g1")
else:
print("Cycle not found in the undirected graph g1")
nodes = 4
g2_undirected = Graph(nodes)
# Undirected graph 2
# 0
# / \
# 1 2
# \ /
# 3
g2_undirected.AddEdge(0, 1, True)
g2_undirected.AddEdge(0, 2, True)
g2_undirected.AddEdge(1, 3, True)
g2_undirected.AddEdge(2, 3, True)
g2_undirected.DetectCycle(0)
if g2_undirected.CyclePresent() == True:
print("Cycle found in the undirected graph g2")
else:
print("Cycle not found in the undirected graph g2")
if __name__ == "__main__":
main()
Output
Cycle not found in the undirected graph g1
Cycle found in the undirected graph g2
#include<iostream>
#include<list>
#include<vector>
#include<stack>
using namespace std;
class Graph {
private:
int nodes;
list<int> *adjlist;
vector<bool> visited;
// parent stores the parent node of the visited node, this is used
// for finding cycle in an un-directed graph.
vector<int> parent;
bool cycle_present;
public:
Graph() {
}
Graph (int arg_nodes) {
this->nodes = arg_nodes;
adjlist = new list<int> [nodes];
visited.resize(nodes, false);
parent.resize(nodes, -1);
cycle_present = false;
}
~Graph () {
delete [] adjlist;
}
void AddEdge (int src, int dst, bool bidirectional) {
adjlist[src].push_back(dst);
if (bidirectional)
adjlist[dst].push_back(src);
}
// Below function detects cycle in an undirected graph
// using depth first search technique at it core.
void DetectCycle (int src) {
visited[src] = true;
for (auto& adj_node : adjlist[src]) {
if (!visited[adj_node]) {
parent[adj_node] = src;
DetectCycle(adj_node);
} else if (parent[src] != adj_node) {
cycle_present = true;
return;
}
}
}
bool CyclePresent () {
return cycle_present;
}
};
int main()
{
Graph g1_undirected (7);
/* Undirected graph 1
0
/ \
1 2
/ \
3 4
/ \
5 6 */
g1_undirected.AddEdge(0, 1, true);
g1_undirected.AddEdge(0, 2, true);
g1_undirected.AddEdge(2, 3, true);
g1_undirected.AddEdge(2, 4, true);
g1_undirected.AddEdge(4, 5, true);
g1_undirected.AddEdge(4, 6, true);
g1_undirected.DetectCycle(0);
if (g1_undirected.CyclePresent()) {
cout << "Cycle found in the undirected graph g1" << endl;
} else {
cout << "Cycle not found in the undirected graph g1" << endl;
}
Graph g2_undirected (4);
/* Undirected graph 2
0
/ \
1 2
\ /
3 */
g2_undirected.AddEdge(0, 1, true);
g2_undirected.AddEdge(0, 2, true);
g2_undirected.AddEdge(1, 3, true);
g2_undirected.AddEdge(2, 3, true);
g2_undirected.DetectCycle(0);
if (g2_undirected.CyclePresent()) {
cout << "Cycle found in the undirected graph g2" << endl;
} else {
cout << "Cycle not found in the undirected graph g2" << endl;
}
return 0;
}
Output
Cycle not found in the undirected graph g1
Cycle found in the undirected graph g2
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
class Graph {
private int nodes;
private List<List<Integer>> adjlist;
private boolean visited[];
// parent stores the parent node of the visited node, this is used
// for finding cycle in an undirected graph.
private int parent[];
private boolean cycle_present;
Graph (int arg_nodes) {
nodes = arg_nodes;
adjlist = new ArrayList<> (nodes);
for (int i=0; i<nodes; i++) {
adjlist.add(new ArrayList<>());
}
visited = new boolean[nodes];
parent = new int[nodes];
Arrays.fill(parent, -1);
cycle_present = false;
}
public void AddEdge (int src, int dst, boolean bidirectional) {
adjlist.get(src).add(dst);
if (bidirectional)
adjlist.get(dst).add(src);
}
// Function detects cycle in an undirected graph using
// DFS technique at its core.
public void DetectCycle (int src) {
visited[src] = true;
for (Integer adj_node : adjlist.get(src)) {
if (!visited[adj_node]) {
parent[adj_node] = src;
DetectCycle(adj_node);
} else if (parent[src] != adj_node) {
cycle_present = true;
return;
}
}
}
public boolean CyclePresent () {
return cycle_present;
}
public static void main (String[] args) {
Graph g1_undirected = new Graph(7);
/* Undirected graph 1
0
/ \
1 2
/ \
3 4
/ \
5 6 */
g1_undirected.AddEdge(0, 1, true);
g1_undirected.AddEdge(0, 2, true);
g1_undirected.AddEdge(2, 3, true);
g1_undirected.AddEdge(2, 4, true);
g1_undirected.AddEdge(4, 5, true);
g1_undirected.AddEdge(4, 6, true);
g1_undirected.DetectCycle(0);
if (g1_undirected.CyclePresent()) {
System.out.println("Cycle found in the undirected graph g1");
} else {
System.out.println("Cycle not found in the undirected graph g1");
}
Graph g2_undirected = new Graph(4);
/* Undirected graph 2
0
/ \
1 2
\ /
3 */
g2_undirected.AddEdge(0, 1, true);
g2_undirected.AddEdge(0, 2, true);
g2_undirected.AddEdge(1, 3, true);
g2_undirected.AddEdge(2, 3, true);
g2_undirected.DetectCycle(0);
if (g2_undirected.CyclePresent()) {
System.out.println("Cycle found in the undirected graph g2");
} else {
System.out.println("Cycle not found in the undirected graph g2");
}
}
}
Output
Cycle not found in the undirected graph g1
Cycle found in the undirected graph g2