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 cases
4.
Solution
5.
Code
5.1.
Python Code
5.2.
Java Code
5.3.
C++ Code
6.
Complexity
7.
Frequently Asked Questions
7.1.
What are graph traversal algorithms?
7.2.
What is a path and cycle in graphs?
7.3.
Name a method to detect cycles in an undirected graph.
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Number of loops of size k starting from a specific node

Author Yashesvinee V
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Undirected graphs have vertices connected in pairs using edges or lines. An edge joins each pair of graph vertices in a complete undirected graph. Since the edges have no defined direction, they can point from one vertex to another or vice versa. Loops or cycles are formed when an edge or sequence of edges point to the same vertex. Loops may involve a single vertex or more. In this blog, we shall see a simple problem statement related to the loops in undirected graphs.

Number of loops of size k starting from a specific node

Problem Statement

Consider a completely connected undirected graph of n nodes. Calculate the number of ways of traversing from one node and returning to it after visiting k number of nodes.

Input: n, k

Output: number of ways to traverse the graph - integer

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 cases

Case 1: n = 3, k = 3

Output: 2

Case 1 where n = 3, k = 3

Case 2: n = 4, k = 2

Output: 3

Case 2 where n = 4, k = 2 

Case 3: n = 4, k = 3

Output: 6

Case 3 where n = 4, k = 3

Case 4: n = 5, k = 2

Output: 4

Case 4 where n = 5, k = 2

Solution

Let f(n, k) be a function to generate the number of ways of traversing the graph by visiting k nodes. As we start from one node and return to it, we visit k-1 nodes, excluding the starting node. Since we exclude the starting node, we have n-1 choices to select the intermediate nodes. So for every intermediate node, there are n-1 options. This suggests that there are n-1k-1 ways. To avoid repeating the edges after every traversal, we subtract f(n, k-1). So the final recursive equation is as follows:

Solution expression

The base case for this equation is f(n, 2) = n - 1. This can be proved by observing cases 2 and 4. Irrespective of the value of n, if k is 2, then the number of ways of traversing is always n-1. Upon expanding the recursive equation, we obtain the following.

Expanded solution

Let the above equation be Eq1. Dividing Eq1 by (n-1) gives the following.

Dividing by n-1

Let this be Eq2. Adding Eq1 and Eq2 results in the following equation.

Adding resulting equations

Solving this further, we obtain the following.

Final equation

Code

Now, let us implement the solution as code in Python, Java and C++.

Python Code

def solution(n,k):    
    x = n-1 
    # if k&1 returns 1, k is odd, else even
    if (k & 1):
        return (pow(x, k) - x) / n
    return (pow(x, k) + x) / n
 
# n,k = map(int,input().split())
n = k = 3
print (int(solution(n, k)))

Java Code

import java.io.*;
public class Main
{
    static int solution(int n,int k)
    {
        int x = n-1;

        // if k&1 returns 1, k is odd, else even
        if ((k & 1) == 1)
            return (int)(Math.pow(x, k) -x) / n;
        return (int)(Math.pow(x, k) + x) / n;
    }
    
    public static void main(String args[])
    {
        int n = 3, k = 3;    
        System.out.println(solution(n, k));
    }
}

C++ Code

#include <bits/stdc++.h>
using namespace std;
int solution(int n, int k)
{
    int x = n-1;
    
    // if k&1 returns 1, k is odd, else even    
    if ((k & 1) == 1)
        return (pow(x, k) - x) / n; 
    return (pow(x, k) + x) / n;
}
 
int main()
{
    int n = 3, k = 3;
    cout << solution(n, k) << endl;
    return 0;
}

Output:

2

Complexity

Time and space complexity is O(1).

Check out this problem - Shortest Common Supersequence.

Frequently Asked Questions

What are graph traversal algorithms?

Breadth-first search and depth-first search are two graph traversal algorithms. In breadth-first search, all adjacent nodes of a single node are visited. In depth-first search, after the adjacent vertices for a starting vertex are found, it moves to that vertex and tries to traverse it similarly.

What is a path and cycle in graphs?

A path defines a sequence of vertices connected by edges. A cycle is a path having the same starting and ending point. 

Name a method to detect cycles in an undirected graph.

We can use BFS, DFS and union-find algorithms to detect cycles in an undirected graph. In the BFS method, for every visited vertex ‘v’, if there is an adjacent vertex ‘u’ such that u is already visited and u is not a parent of v, there is a cycle in the graph. If there is no such adjacent for any vertex, there is no cycle. 

Conclusion

This blog discusses how to find the number of loops of size k starting from a specific node in a completely connected undirected graph. Check out our articles on Detecting cycles in a directed graphdetecting cycles in an undirected graph and properties of graphs. Explore our Library on Coding Ninjas Studio to gain knowledge on Data Structures and Algorithms, Machine Learning, Deep Learning, Cloud Computing and many more! Test your coding skills by solving our test series and participating in the contests hosted on Coding Ninjas Studio! 

Looking for questions from tech giants like Amazon, Microsoft, Uber, etc.? Look at the problems, interview experiences, and interview bundle for placement preparations. Upvote our blogs if you find them insightful and engaging! Happy Coding!

Thank you

Previous article
Identify Same Contacts in a List of Contacts
Next article
Reverse Delete Algorithm
Live masterclass