Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Sample Example
4.
Approach
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in c++
4.4.
Implementation in Python
4.5.
Time Complexity
4.6.
Space complexity
5.
Frequently Asked Questions
5.1.
What do you mean by connected graph?
5.2.
What are undirected graphs? 
5.3.
What are the approaches of graph traversal?
5.4.
What is time complexity?
5.5.
What is space complexity?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count of Simple Cycles in a Connected Undirected Graph Having N Vertices

Author Aditya Gupta
2 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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. 
 

Count of Simple Cycles in a Complete undirected graph

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.

Input:

Edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (5, 6), (5, 7), (6, 7)]

example

Output: 

The number of cycles in the graph is 2.

Explanation: 

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 visitedvistime 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)]

example
  • 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:

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:

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.

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

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 problemsinterview experiences, and interview bundles for placement preparations.

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

Happy Learning!

Previous article
Count the nodes within K-distance from all nodes in a set
Next article
Count Number of Edges in an Undirected Graph
Live masterclass