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;
}
You can also try this code with Online C++ Compiler
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));
}
}
You can also try this code with Online Java Compiler
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))
You can also try this code with Online Python Compiler
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 Traversal, Regular 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 Algorithms, Competitive Programming, JavaScript, System 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!
244+ registered 
