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.

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

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:

0 -> 1 -> 3 -> 4 -> 2 => 23

0 -> 1 -> 4 -> 2 => 17

0 -> 1 -> 4 -> 3 => 24

0 -> 2 -> 4 -> 3 => 19

0 -> 2 -> 4 -> 1 -> 3 => 29

0 -> 4 -> 1 -> 3 => 26

0 -> 4 -> 2 => 9

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

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.

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: