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.
Example
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Algorithm
4.1.
C++ Code
4.2.
Python Code
4.3.
Input
4.4.
Output
5.
Complexities
5.1.
Time complexity
5.2.
Space complexity
6.
Frequently Asked Questions
6.1.
Why do we need backtracking?
6.2.
What are the limitations of backtracking?
6.3.
What are the advantages of using backtracking?
6.4.
What do you mean by a simple path in a graph?
6.5.
Is backtracking recursive?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if there is a path of more than k length from a source

Author Manan Singhal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Backtracking tries to search for every possible combination of solutions at each step to solve. We have three different types of classic problems in backtracking, which are as follows: Enumeration problems, Decision problems, and Optimization problems.

Backtracking

Problem Statement

You have been given a graph, a source vertex in the graph, and a number k. You need to find if it is possible to get a non-cyclic graph starting from the given source and ending at any other vertex such that the distance from the source to that vertex is at least k length.

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

Example

Input

Input graph
source vertex = 0, k = 15
source vertex = 0, k = 31

Output

Yes
No

Explanation

In the given input graph, all the possible paths will be:

  1. 0 -> 1 -> 3 -> 4 -> 2 => 23
  2. 0 -> 1 -> 4 -> 2 => 17
  3. 0 -> 1 -> 4 -> 3 => 24
  4. 0 -> 2 -> 4 -> 3 => 19
  5. 0 -> 2 -> 4 -> 1 -> 3 => 29
  6. 0 -> 4 -> 1 -> 3 => 26
  7. 0 -> 4 -> 2 => 9
  8. 0 -> 4 -> 3 -> 1 => 24
     

The longest path as compared to distance will be 0 -> 2 -> 4 -> 1 -> 3. The distance, when you calculate, will come out to be 29. So, the output should be false for any value greater than 29.

Algorithm

With the help of backtracking, we solve this problem. We start from the source mentioned in the problem and explore all paths from that source or the current vertex. We keep a variable to track the distance covered from the source. If the distance becomes more than k, we return yes, or if no such path exists, we backtrack.

Let's start with the implementation of the code.

C++ Code

/* C++ Program: Check if there is a path of more than k length from a source */
#include<bits/stdc++.h>

using namespace std;

int vertices = 5;
typedef pair<int, int> iPair;
list<pair<int, int>> *adjacent = new list<iPair> [vertices];;

/* used to create an input graph */
void addEdge(int source, int destination, int distance) {
    adjacent[source].push_back(make_pair(destination, distance));
	adjacent[destination].push_back(make_pair(source, distance));
}

bool func(int sourceVertex, int k, vector<bool> &pathArray) {
    
    list<iPair>::iterator i;
	for (i=adjacent[sourceVertex].begin(); i!=adjacent[sourceVertex].end(); ++i) {
    	
		/* Getting adjacent vertex */
		int adjacentVertex = (*i).first;

		/* Getting corresponding distance */
		int distance = (*i).second;

		if (pathArray[adjacentVertex] == true)
			continue;

		if (distance >= k)
			return true;

		pathArray[adjacentVertex] = true;

		if (func(adjacentVertex, k-distance, pathArray))
			return true;

		pathArray[adjacentVertex] = false;
	}

	return false;
}

 
/* the main function returns true if such a path is possible */
bool checkPathWithLengthKOrMore(int sourceVertex, int k) {
    if (k <= 0) {
        return true;
    }
    
    vector<bool> pathArray(vertices, false);
    
	/* Adding source vertex to path */
	pathArray[sourceVertex] = 1;

	return func(sourceVertex, k, pathArray);
}

/* Main program */
int main() {
    
	/* creating the graph as shown in the input figure */
	addEdge(0, 1, 4);
	addEdge(0, 2, 8);
	addEdge(0, 4, 7);
	addEdge(1, 3, 8);
	addEdge(1, 4, 11);
	addEdge(2, 4, 2);
	addEdge(3, 4, 9);

	if (checkPathWithLengthKOrMore(0, 15)) {
    	cout << "Yes\n";
	}
	else {
    	cout << "No\n";
	}

	if (checkPathWithLengthKOrMore(0, 31)) {
    	cout << "Yes\n";
	}
	else {
    	cout << "No\n";
	}

	return 0;
}

Python Code

# Python Program: Check if there is a path of more than k length from a source

vertices = 15
adjacent = [[] for i in range(vertices)]

# used to create an input graph
def addEdge(source, destination, distance):
	adjacent[source].append([destination, distance])
	adjacent[destination].append([source, distance])

# the main function returns true if such a path is possible
def checkPathWithLengthKOrMore(sourceVertex, k):
    if (k <= 0):
        return True;
    pathArray = [False]*vertices
    
    # Adding source vertex to path
    pathArray[sourceVertex] = 1
    
    return func(sourceVertex, k, pathArray)
    
def func(sourceVertex, k, pathArray):
    i=0;
    while i != len(adjacent[sourceVertex]):
        
        # Getting adjacent vertex
        adjacentVertex = adjacent[sourceVertex][i][0]
        
        # Getting corresponding distance
        distance = adjacent[sourceVertex][i][1]
        i += 1
        
        if (pathArray[adjacentVertex] == True):
            continue
        
        if (distance >= k):
            return True
            
        pathArray[adjacentVertex] = True
        
        if (func(adjacentVertex, k-distance, pathArray)):
            return True
            
        pathArray[adjacentVertex] = False
        
    return False;

 
# Main program
if __name__ == '__main__':

	# creating the graph as shown in the input figure
	addEdge(0, 1, 4)
	addEdge(0, 2, 8)
	addEdge(0, 4, 7)
	addEdge(1, 3, 8)
	addEdge(1, 4, 11)
	addEdge(2, 4, 2)
	addEdge(3, 4, 9)

    # printing the desired output
	if checkPathWithLengthKOrMore(0, 15):
		print("Yes")
	else:
		print("No")

	if checkPathWithLengthKOrMore(0, 31):
		print("Yes")
	else:
		print("No")

Input

Input
source vertex = 0, k = 15
source vertex = 0, k = 31

Output

Yes
No

Complexities

Time complexity

O(N!), where N means the number of the vertex in the graph.

Reason: In the worst case, we must traverse every possible path. This occurs when each node is interconnected with the other. Let’s start from the source node we have n-1 adjacent nodes for the worst-case scenario. The time required for a path to connect will be 2. After selecting a node out of n-1 adjacent nodes, we are left with n-2 adjacent nodes and so on at every step of selecting a node, our selection reduces by 1 node. So, the time complexity of this algorithm is 2(n-1)*(n-1)!, which can be written as O(n!).

Space complexity

O(N), where N means the number of the vertex in the graph.

Reason: We need an array of size N to save pathArray and adjacent vertex count to keep track of the movement of the graph.

Check out this problem - 8 Queens Problem

Frequently Asked Questions

Why do we need backtracking?

Crosswords, verbal arithmetic, Sudoku, and many other puzzles that need constraint fulfillment can all be solved using backtracking. It is frequently the most practical technique for parsing the knapsack problem and other combinatorial optimization issues.

What are the limitations of backtracking?

Backtracking has the disadvantage of requiring extra work. Even if conflicting values for variables are found during intelligent backtracking, they are not stored for quick detection of the same conflict in a subsequent calculation.

What are the advantages of using backtracking?

Due to its brute-force approach, backtracking can almost fix all possible problems. This can be used to find all the possible solutions which exist.

What do you mean by a simple path in a graph?

A simple path in geometry is a simple curve, precisely a continuous injective function from an actual number interval to a metric space, topological space, or, more generally. A simple path in graph theory is a path through a graph that doesn't have recurring vertices.

Is backtracking recursive?

Backtracking can also be referred to as a type of recursion. This is because until we either find the solution or reach the final state, the process of selecting the best possible outcome from the available outcome is repeated.

Conclusion

In the article, we have to check if there is a path of more than k length from a source. We hope this article will help you understand the concept of Backtracking. Check out our other blogs on this topic:

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Alien Dictionary
Next article
Minimum steps to reach target
Live masterclass