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

Malay Gain
Last Updated: Jun 23, 2022
Difficulty Level :
MEDIUM

Introduction

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. Here, we will see how to count the number of such cycles present in the undirected graph.

Problem statement

You are given a connected undirected graph; you need to count the number of simple cycles in the undirected graph.

Input:

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

Graph after connecting the edges

 

Output:

number of cycles in the undirected graph: 2

 

Note: Please try to solve the problem first and then see the solution below.

Approach

We will be using DFS and graph coloring properties to count the number of cycles in the undirected graph.

Algorithm

  • We will maintain a color[ ] array that stores the color of each vertex and par[ ] array that stores the parent of each vertex of the graph.
  • We will use the DFS (depth-first-search) approach to visit every vertex of the graph.
  • If any vertex is visited for the first time, it will be marked as partially visited along with its vertices connected with it.
  • During a recursive DFS call for a vertex, if it is found partially visited, we will increment the count of the cycle number which stores the number of cycles in the undirected graph.
  • If all connected nodes are visited from a vertex, then we will mark the vertex as fully visited.
  • If any fully visited vertex is found, we will skip that node.

 

//function based on the above algorithm

 

void DFSCycle(int u, int p, int color[], int par[], int& cyclenumber){

 

   //the node is already considered

   if (color[u] == 2) {

      return;

   }

   

   //partially visited node found i.e new cycle found

   if (color[u] == 1) {

      cyclenumber++;

     

      return;

   }

   

   //storing parent of u

   par[u] = p;

   

   //marking as partially visited

   color[u] = 1;

   for (int v : graph[u]) {

   

      if (v == par[u]) {

         continue;

      }

      DFSCycle(v, u, color, par, cyclenumber);

   }

 

Code

// C++ implementation for counting the number of cycles in the undirected graph

#include <bits/stdc++.h>
using namespace std;

 // number of vertices i the graph
const int N = 7;

//adjacency list of the connected undirected graph
vector<int> graph[N];

void DFSCycle(int u, int p, int color[], int par[], int& cyclenumber){

   //the node is already considered
   if (color[u] == 2) {
      return;
   }
   
   //partially visited node found i.e new cycle found
   if (color[u] == 1) {
      cyclenumber++;
     
      return;
   }
   
   //storing parent of u
   par[u] = p;
   
   //marking as partially visited
   color[u] = 1;
   for (int v : graph[u]) {
   
      if (v == par[u]) {
         continue;
      }
      DFSCycle(v, u, color, par, cyclenumber);
   }
   
   //marking as fully visited
   color[u] = 2;
}

// function for connecting edges in the graph
void insert(int u, int v){
   graph[u].push_back(v);
   graph[v].push_back(u);
}

int main(){

 //edges in the graph
   insert(1, 2);
   insert(2, 3);
   insert(3, 4);
   insert(4, 5);
   insert(5, 2);
   insert(5, 6);
   insert(5, 7);
   insert(6, 7);
   
   int color[N];
   int par[N];

   int cyclenumber = 0;
  
   
   DFSCycle(1, 0, color,par, cyclenumber);
   
    cout<<"count of cycles in the undirected graph : "<<cyclenumber;
   
}

 

Output

count of cycles in the undirected graph : 2

 

Complexity Analysis

Time Complexity

Here for finding the number of cycles in the undirected graph, 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  is O(V) as extra color[ ] and par[ ]  is used here.

Frequently Asked Questions

What is a connected graph?

A graph is connected if there is a path between every pair of vertices in the graph.

What is the difference between a directed and undirected graph?

The main difference between a directed and undirected graph is that edges in a directed graph have a specific direction (one-directional), but edges in an undirected graph are bidirectional.

What are the approaches of graph traversal?

There is mainly two approaches are used to traverse a graph
DFS(depth-first-search)
BFS(breadth-first-search)

What is the application of graph coloring?

It is used in Sudoku problem solving, and map coloring for assigning mobile radio frequencies to towers.

Conclusion

This article covered how to count the number of simple cycles in a connected undirected graph having N vertices.

Check out the CodeStudio library for getting a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in CodeStudio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

 

Happy learning!

 

 

Was this article helpful ?
1 upvote