Cycle in undirected graphs can be detected easily using a depth-first search traversal. 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 of detecting cycles in an undirected graph using depth-first search traversal**

**Algorithm : DFS Detect Cycle In An Undirected Graph (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

4. Set parent [adjacent_node] = source_node.

5. **DFS Detect Cycle In An Undirected Graph (adjacent_node)**

6. **Else If** the parent[source_node] != adjacent_node

7. Cycle found. Return.

**Time complexity of detecting cycles in an undirected graph using depth-first search : 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(2E+V) for a directed graph.

**Python**

**Java**

**C++14 program for detecting cycle in an undirected graph using Depth First Search (DFS) algorithm**

```
#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);
}
// Function detects cycle in an undirected graph
//
void DFS_DetectCycleInUndirectedGraph (int src) {
visited[src] = true;
for (auto& adj_node : adjlist[src]) {
if (!visited[adj_node]) {
parent[adj_node] = src;
DFS_DetectCycleInUndirectedGraph (adj_node);
} else if (parent[src] != adj_node) {
cycle_present = true;
return;
}
}
}
bool IsCyclePresent() {
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.DFS_DetectCycleInUndirectedGraph(0);
if (g1_undirected.IsCyclePresent()) {
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.DFS_DetectCycleInUndirectedGraph(0);
if (g2_undirected.IsCyclePresent()) {
cout << "Cycle found in the undirected graph g2" << endl;
} else {
cout << "Cycle not found in the undirected graph g2" << endl;
}
return 0;
}
```

Output showing detecting of cycles in an undirected graph using depth-first search traversal

```
Cycle not found in the undirected graph g1
Cycle found in the undirected graph g2
```

All rights reserved.