Hey Ninjas!Graphs are one of the most important data structures. One of the oldest problems in graph theory is counting the number of cycles in a connected undirected graph with n vertices. A cycle consists of at least three vertices connected in a loop through the edges. In an undirected graph, there can be multiple such cycles that may exist.

The problem of counting cycles in a graph is challenging because the number of cycles in a graph can grow exponentially with the number of vertices, making brute-force methods impractical for large graphs. Here, we will see how to count the number of such cycles present in the undirected graph with an example and implementation.

Problem Statement

You are given a connected undirected graph with N vertices. You need to count the number of cycles in this graph.

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

Sample Example

We will take an example so the problem statement will be clear for you.

One cycle is formed from the vertices (2, 3, 4, 5) and one from (5, 6, 7). So the total number of cycles in the graph is 2.

Approach

We will use DFS Algorithm and graph properties to count the number of cycles in the undirected graph.

Algorithm

We will use the DFS (depth-first-search) approach to visit every graph vertex.

We will maintain a visited[]array that checks if the vertex is visited and a vistime[]array that stores the time when each vertex of the graph is marked visited or the DFS visit time of each node.

We define an integer timer to keep track of the DFS visit time.

If any vertex is visited for the first time, it will be marked as visited, vistime of the vertex will be updated.

For each visited vertex v, check its adjacent vertices. If an adjacent vertex u is already visited and is not the parent of v, and vistime(visited time) of vertex u is less than vertex v, a cycle exists between v and u.

If any fully visited vertex is found, we will skip that node.

Dry Run

We have covered the problem statement, example, and algorithm. Now, let's discuss the above algorithm using an input value, i.e., dry run.

let the input be, edges= [(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (5, 6), (5, 7), (6, 7)]

The cycle count is currently 0, and no vertex is visited. the timer is also currently 0.

We start the DFS traversal from vertex 1.

Vertex 1 is added to the visited list vistime of vertex 1 is 0, the timer is incremented to 1, and only adjacent vertex 2 is visited. The parent of vertex two is set to 1.

Vertex 2 is added to the visited, vistime of vertex 2 is 1, and the timer is incremented to 2. Its adjacent vertex is 1, 3, 5 as 1 is previously visited, and the parent of 2 is 1, so we will skip calling the DFS traversal again on 1. we call the DFS traversal on 3. The parent of vertex 3 is set to 2.

Vertex 3 is added to the visited, vistime of vertex 3 is 2. The timer is incremented to 3. Its adjacent vertex is 2, 4 as 2 is previously visited, and the parent of 3 is 2, so we will skip calling the DFS traversal again on 2. we call the DFS traversal on 4. The parent of vertex 4 is set to 3.

Vertex 4 is added to the visited, vistime of vertex 4 is 3. The timer is incremented to 4, its adjacent vertex is 3, 4 as 3 is previously visited, and the parent of 4 is 3, so we will skip calling the DFS traversal again on 3. we call the DFS traversal on 5. The parent of vertex 5 is set to 4.

We continue the DFS traversal from vertex 5, vistime of vertex 5 is 4, and the timer is incremented to 5. Its adjacent vertex is 2, 4, 6, 7, as 2 is previously visited. The parent of 5 is not 2, also vistime of 2 is less than 5. We find out the presence of the cycle and increment the cycle count to 1. so we will skip calling the DFS traversal again on 2, 4 is previously visited, and the parent of 5 is 4, so we will skip calling the DFS traversal again on 4 and visit its remaining adjacent vertices 6 and 7.

Vertex 6 is added to visited, vistime of vertex 6 is 5, and the timer is incremented to 6. Its adjacent vertex is 5, 7 as 5 is previously visited, and the parent of 6 is 5, so we will skip calling the DFS traversal again on 5. we call the DFS traversal on 7. The parent of vertex 7 is set to 6.

Vertex 7 is added to visited, vistime of vertex 7 is 6, and the timer is incremented to 7. Its adjacent vertex 5 is already visited and is not its parent, and vistime of 5 is less than the vistime of 7, so we find out the presence of the cycle and increment the cycle count to 2.

We have visited all vertices, so the DFS traversal is complete.

The cycle count is 2, which is the final answer.

Therefore, the given graph has two cycles.

Implementation in c++

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
vector<int> visited;
vector<vector<int>> graph;
vector<int> vistime;
int timer = 0;
void dfs(int vertex, int parent, int &cycle_count){
visited[vertex] = 1;
vistime[vertex] = timer;
timer++;
for (auto child : graph[vertex]) {
if (child == parent){
continue;
}
if (!visited[child]){
dfs(child, vertex, cycle_count);
}
else{
if (child != parent && vistime[child] < vistime[vertex]){
cycle_count++;
}
}
}
}
int main(){
vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 2}, {5, 6}, {5, 7}, {6, 7}};
int n = 7;
graph.resize(n + 1);
for (auto edge : edges){
int vertex1 = edge.first;
int vertex2 = edge.second;
graph[vertex1].push_back(vertex2);
graph[vertex2].push_back(vertex1);
}
visited.assign(n + 1, 0);
int cycle_count = 0;
vistime.resize(n + 1);
dfs(1, -1, cycle_count);
cout << "The number of cycles present is" << " " << cycle_count << endl;
return 0;
}

Output:

Implementation in Python

from collections import defaultdict
graph = defaultdict(list)
visited = []
vistime = []
timer = 0
def dfs(vertex, parent, cycle_count):
global timer
visited[vertex] = 1
vistime[vertex] = timer
timer += 1
for child in graph[vertex]:
if child == parent:
continue
if not visited[child]:
dfs(child, vertex, cycle_count)
else:
if child != parent and vistime[child] < vistime[vertex]:
cycle_count[0] += 1
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (5, 6), (5, 7), (6, 7)]
n = 7
for edge in edges:
vertex1, vertex2 = edge
graph[vertex1].append(vertex2)
graph[vertex2].append(vertex1)
visited = [0] * (n + 1)
cycle_count = [0]
vistime = [0] * (n + 1)
dfs(1, -1, cycle_count)
print("The number of cycles present is", cycle_count[0])

Output:

Time Complexity

Here for finding the number of cycles in the undirected graph, the time complexity is the same as DFS traversal, i.e., O( V + E ), where V is the number of vertices and E is the number of edges in the graph.

Space complexity

O( V ) as extra visited[ ] and vistime[ ]is used here where V is the number of vertices. Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

What do you mean by connected graph?

A graph is connected if at least one single path joins each pair of vertices.

What are undirected graphs?

An undirected graph is a set of vertices or nodes that are connected together, where all the edges are bidirectional.

What are the approaches of graph traversal?

Two approaches are mainly used to traverse a graph

DFS(depth-first-search) and BFS(breadth-first-search).

What is time complexity?

The time an algorithm or code takes to execute each instruction is known as its time complexity.

What is space complexity?

The total memory space used by an algorithm or code, including the space of input values, is referred to as "space complexity".

Conclusion

This article discusses the topic of the count of cycles in connected undirected graphs. In detail, we have seen the problem statement, sample example, algorithm, dry run, and implementation in two languages. Along with this, we also saw the time and space complexity.

We hope this blog has helped you enhance your knowledge of the count of cycles in a connected undirected graph. If you want to learn more, then check out our articles.

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!