Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Example
2.
Algorithm
3.
Code👨‍💻
4.
Complexity
5.
Frequently Asked Questions
5.1.
What is DFS used for?
5.2.
Why is DFS better than BFS?
5.3.
What is the time complexity of DFS?
5.4.
What is a cycle in a directed graph?
5.5.
Is DFS linear time?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count Cycles of Length n in an Undirected and Connected Graph

Author soham Medewar
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Consider a connected and undirected graph having V vertices. You have to return the count of a total number of cycles having length n. The cycle of length n means the cycle has n edges and n vertices within the cycle. Let us see a sample test case to understand the problem statement.

Example

graph

Input

4
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0


In the above input, the first line takes input n. The next V line contains a matrix representation of a graph. Zero indicates that there is no edge between the ith and jth node. One indicates that there is an edge between the ith and jth node.

Output

3


Explanation

In the above example, the output is 3. The above graph has three cycles of length 4. The cycles are as follows:

First cycle: 1 -> 2 -> 3 -> 0 -> 1

Second cycle: 1 -> 4 -> 3 -> 0 -> 1

Third cycle: 1 -> 2 -> 3 -> 4 -> 1

Three cycles

Algorithm

🟢We can solve this problem by using a depth-first search algorithm. With the help of DFS Algorithm, we can find every possible path of length n-1 from a particular point (source point). After finding the path, we check whether the path ends with the vertex we started. If the path ends with starting vertex, then we count it as a cycle. Observe that we are looking for the path of length n-1 because the last edge (nth) edge will be a closing edge. 

🟣We can find every possible path of length n-1 by using V - (n - 1) vertices. Here V is the number of vertices in the graph.

🟢In the above example, we can find all the cycles of length four using 2 (5 - (4 - 1)) vertices. The logic behind this statement is very simple. This may be explained rather simply by the fact that we utilize these 2 vertices to look for any path of length (n-1) = 3 that includes the remaining 3 vertices. Therefore, utilizing only the remaining 3 vertices does not allow us to build a cycle of length 4 because these 2 vertices also cover the cycles of the remaining 3 vertices.

🟣One more thing to notice is that each vertex will give a duplicate cycle for every cycle we form. For example, cycle 1 -> 2 -> 3 -> 0 -> 1 and cycle 1 -> 0 -> 3 -> 2 -> 1 are same. One cycle will be clockwise, and another will be anti-clockwise. Hence total count of cycles should be divided by 2.

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

Code👨‍💻

C++

#include <bits/stdc++.h>
using namespace std;
 
/* total number of vertices in the graph g */
const int V = 5;
 
/* n is the length of the cycle. */


void dfs(bool g[][V], bool vis[], int n,
               int ver, int start, int &cnt)
{
    /* mark the vertex ver as vis */
    vis[ver] = true;
 
    /* n-1 path length is found */
    if (n == 0) {
 
        /* mark ver as un-visited to make it usable again. */
        vis[ver] = false;
 
        /* Check if vertex ver can end with vertex start */
        if (g[ver][start])
        {
            cnt++;
            return;
        } else
            return;
    }
 
    /* searching every path of length (n-1) */
    for (int i = 0; i < V; i++)
        if (!vis[i] && g[ver][i])
 
            /* dfs for searching path by decreasing length by 1 */
            dfs(g, vis, n-1, i, start, cnt);
 
    /* marking ver as unvisited to make it usable again. */
    vis[ver] = false;
}
 
/* Counts cycles of length N in an undirected and connected graph. */
int countingCycles(bool g[][V], int n)
{
    /* all vertex are marked un-visited initially. */
    bool vis[V];
    memset(vis, 0, sizeof(vis));
 
    /* using v-n+1 vertices to search a cycle */
    int cnt = 0;
    for (int i = 0; i < V - (n - 1); i++) {
        dfs(g, vis, n-1, i, i, cnt);
 
        /* ith vertex is marked as visited and
        will not be visited again. */
        vis[i] = true;
    }
 
    return cnt/2;
}
 
int main()
{
    bool g[][V] = {{0, 1, 0, 1, 0},
                    {1, 0, 1, 0, 1},
                    {0, 1, 0, 1, 0},
                    {1, 0, 1, 0, 1},
                    {0, 1, 0, 1, 0}};
    int n = 4;
    cout<<"Total cycles of length "<<n<<" are "<<countingCycles(g, n);
    return 0;
}


Java

/* Java program to calculate cycles
 of length n in a given graph g */
public class Main {
     
    /* Number of vertices */
    public static final int V = 5;
    static int cnt = 0;
     
    static void DFS(int g[][], boolean vis[],
                    int n, int ver, int st) {
         
        /* mark the vertex ver as visited */
        vis[ver] = true;
         
        /* n-1 path length is found */
        if (n == 0) {
             
            /* mark ver as un-visited to make it usable again */
            vis[ver] = false;
             
            /* Check if vertex ver end with vertex st*/
            if (g[ver][st] == 1) {
                cnt++;
                return;
            } else
                return;
        }
         
        /* searching for n-1 path length */
        for (int i = 0; i < V; i++)
            if (!vis[i] && g[ver][i] == 1)
             
                /* DFS for searching path by decreasing length by 1 */
                DFS(g, vis, n-1, i, st);
         
        /* marking ver as unvisited to make it usable again */
        vis[ver] = false;
    }
     
    /* counting cycles of length N */
    static int countingCycles(int g[][], int n) {
         
        /* all vertex are marked un-visited initially. */
        boolean vis[] = new boolean[V];
         
        /* Searching for cycle by using v-n+1 vertices */
        for (int i = 0; i < V - (n - 1); i++) {
            DFS(g, vis, n-1, i, i);
             
            /*ith vertex is marked as visited and will not be visited again.*/
            vis[i] = true;
        }
         
        return cnt / 2;
    }
     
    /* driver code */
    public static void main(String[] args) {
        int g[][] = {{0, 1, 0, 1, 0},
                        {1, 0, 1, 0, 1},
                        {0, 1, 0, 1, 0},
                        {1, 0, 1, 0, 1},
                        {0, 1, 0, 1, 0}};
         
        int n = 4;
         
        System.out.println("Total cycles of length "+n+" are "+countingCycles(g, n));
    }
}


Python

""" Number of vertices """
V = 5
 
def dfs(g, vis, n, ver, st, cnt):
 
    """ mark the vertex ver as visited """
    vis[ver] = True
  
    # n-1 path length is found
    if n == 0:
 
        """ mark ver as un-visited to make it usable again """
        vis[ver] = False
  
        """ Check if vertex ver can end with vertex st """
        if g[ver][st] == 1:
            cnt = cnt + 1
            return cnt
        else:
            return cnt
  
    """ For searching every possible path of length (n-1) """
    for i in range(V):
        if vis[i] == False and g[ver][i] == 1:
 
            """ dfs for searching path by decreasing length by 1 """
            cnt = dfs(g, vis, n-1, i, st, cnt)
  
    """ marking ver as unvisited to make it usable again """
    vis[ver] = False
    return cnt
  
""" Counts cycles of length n """
def countingCycles( g, n):
 
    """ all vertex are marked un-visited initially."""
    vis = [False] * V
  
    """ Searching for cycle by using v-n+1 vertices """
    cnt = 0
    for i in range(V-(n-1)):
        cnt = dfs(g, vis, n-1, i, i, cnt)
  
        """ ith vertex is marked as visited and will not be visited again. """
        vis[i] = True
     
    return int(cnt/2)
  
""" main : """
g = [[0, 1, 0, 1, 0],
         [1 ,0 ,1 ,0, 1],
         [0, 1, 0, 1, 0],
         [1, 0, 1, 0, 1],
         [0, 1, 0, 1, 0]]
           
n = 4
print("Total cycles of length ",n," are ",countingCycles(g, n))

Complexity

Time: We basically use DFS in the code so the time complexity will be O(V + E). Where V is a total number of vertices and E is the total number of Edges.

Space: The space complexity will be O(V).

You can also read Detect cycle in an undirected graph here.

Frequently Asked Questions

What is DFS used for?

Depth-first search is used in cycle detection in graphs, scheduling problems, topological sorting, and solving puzzles with only one solution, such as a maze or a sudoku puzzle. Other applications involve analyzing networks, for example, testing if a graph is bipartite.

Why is DFS better than BFS?

The shortest path is discovered by DFS using Stack. When the target is nearer the source, BFS works better. When the target is far from the source, DFS is superior. BFS is not appropriate for decision trees used in puzzle games because it takes into account every neighbour.

What is the time complexity of DFS?

The temporal complexity of DFS is O(V), where V is the number of vertices when the full graph is traversed.

What is a cycle in a directed graph?

A cycle in graph theory is a path that originates at one vertex and terminates at the same vertex.

Is DFS linear time?

As a result, there is no real difference between the actual runtime of DFS and BFS: both algorithms take linear time, with the only minor difference being the number of edges (or the length of the adjacency linked list) of the graph, depending on whether it is directed or undirected. 

Conclusion

In the above article, we have discussed the problem of counting the total number of cycles of length n in an undirected connected graph having vertices V. If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder TraversalRegular and Bipartite graphs, and Planar and Non-Planar Graphs.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive 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!

Happy Coding!

Previous article
Find Number of Islands
Next article
Check if there is a Cycle with Odd Weight Sum in an Undirected Graph.
Live masterclass