Given a directed graph, a source vertex ‘src’ and a destination vertex ‘dst’, print all paths from given ‘src’ to ‘dst’.
Consider the following directed graph. Let the src be 2 and dst be 3. There are 3 different paths from 2 to 3.
We have already discussed Print all paths from a given source to a destination using DFS.
Below is BFS based solution.
Algorithm :
create a queue which will store path(s) of type vector
initialise the queue with first path starting from src
Now run a loop till queue is not empty
get the frontmost path from queue
check if the lastnode of this path is destination
if true then print the path
run a loop for all the vertices connected to the
current vertex i.e. lastnode extracted from path
if the vertex is not visited in current path
a) create a new path from earlier path and
append this vertex
b) insert this new path to queue
Implementation:
C++
// C++ program to print all paths of source to// destination in given graph#include <bits/stdc++.h>using namespace std;// utility function for printing// the found path in graphvoid printpath(vector<int>& path){ int size = path.size(); for (int i = 0; i < size; i++) cout << path[i] << " "; cout << endl;}// utility function to check if current// vertex is already present in pathint isNotVisited(int x, vector<int>& path){ int size = path.size(); for (int i = 0; i < size; i++) if (path[i] == x) return 0; return 1;}// utility function for finding paths in graph// from source to destinationvoid findpaths(vector<vector<int> >& g, int src, int dst, int v){ // create a queue which stores // the paths queue<vector<int> > q; // path vector to store the current path vector<int> path; path.push_back(src); q.push(path); while (!q.empty()) { path = q.front(); q.pop(); int last = path[path.size() - 1]; // if last vertex is the desired destination // then print the path if (last == dst) printpath(path); // traverse to all the nodes connected to // current vertex and push new path to queue for (int i = 0; i < g[last].size(); i++) { if (isNotVisited(g[last][i], path)) { vector<int> newpath(path); newpath.push_back(g[last][i]); q.push(newpath); } } }}// driver programint main(){ vector<vector<int> > g; // number of vertices int v = 4; g.resize(4); // construct a graph g[0].push_back(3); g[0].push_back(1); g[0].push_back(2); g[1].push_back(3); g[2].push_back(0); g[2].push_back(1); int src = 2, dst = 3; cout << "path from src " << src << " to dst " << dst << " are \n"; // function for finding the paths findpaths(g, src, dst, v); return 0;} |
Java
// Java program to print all paths of source to// destination in given graphimport java.io.*;import java.util.*;class Graph{// utility function for printing// the found path in graphprivate static void printPath(List<Integer> path){ int size = path.size(); for(Integer v : path) { System.out.print(v + " "); } System.out.println();}// Utility function to check if current// vertex is already present in pathprivate static boolean isNotVisited(int x, List<Integer> path){ int size = path.size(); for(int i = 0; i < size; i++) if (path.get(i) == x) return false; return true;}// Utility function for finding paths in graph// from source to destinationprivate static void findpaths(List<List<Integer> > g, int src, int dst, int v){ // Create a queue which stores // the paths Queue<List<Integer> > queue = new LinkedList<>(); // Path vector to store the current path List<Integer> path = new ArrayList<>(); path.add(src); queue.offer(path); while (!queue.isEmpty()) { path = queue.poll(); int last = path.get(path.size() - 1); // If last vertex is the desired destination // then print the path if (last == dst) { printPath(path); } // Traverse to all the nodes connected to // current vertex and push new path to queue List<Integer> lastNode = g.get(last); for(int i = 0; i < lastNode.size(); i++) { if (isNotVisited(lastNode.get(i), path)) { List<Integer> newpath = new ArrayList<>(path); newpath.add(lastNode.get(i)); queue.offer(newpath); } } }}// Driver codepublic static void main(String[] args){ List<List<Integer> > g = new ArrayList<>(); int v = 4; for(int i = 0; i < 4; i++) { g.add(new ArrayList<>()); } // Construct a graph g.get(0).add(3); g.get(0).add(1); g.get(0).add(2); g.get(1).add(3); g.get(2).add(0); g.get(2).add(1); int src = 2, dst = 3; System.out.println("path from src " + src + " to dst " + dst + " are "); // Function for finding the paths findpaths(g, src, dst, v);}}// This code is contributed by rajatsri94 |
Python3
# Python3 program to print all paths of # source to destination in given graphfrom typing import Listfrom collections import deque# Utility function for printing# the found path in graphdef printpath(path: List[int]) -> None: size = len(path) for i in range(size): print(path[i], end = " ") print()# Utility function to check if current# vertex is already present in pathdef isNotVisited(x: int, path: List[int]) -> int: size = len(path) for i in range(size): if (path[i] == x): return 0 return 1# Utility function for finding paths in graph# from source to destinationdef findpaths(g: List[List[int]], src: int, dst: int, v: int) -> None: # Create a queue which stores # the paths q = deque() # Path vector to store the current path path = [] path.append(src) q.append(path.copy()) while q: path = q.popleft() last = path[len(path) - 1] # If last vertex is the desired destination # then print the path if (last == dst): printpath(path) # Traverse to all the nodes connected to # current vertex and push new path to queue for i in range(len(g[last])): if (isNotVisited(g[last][i], path)): newpath = path.copy() newpath.append(g[last][i]) q.append(newpath)# Driver codeif __name__ == "__main__": # Number of vertices v = 4 g = [[] for _ in range(4)] # Construct a graph g[0].append(3) g[0].append(1) g[0].append(2) g[1].append(3) g[2].append(0) g[2].append(1) src = 2 dst = 3 print("path from src {} to dst {} are".format( src, dst)) # Function for finding the paths findpaths(g, src, dst, v)# This code is contributed by sanjeev2552 |
C#
// C# program to print all paths of source to// destination in given graphusing System;using System.Collections.Generic;public class Graph{// utility function for printing// the found path in graphstatic void printPath(List<int> path){ int size = path.Count; foreach(int v in path) { Console.Write(v + " "); } Console.WriteLine();}// Utility function to check if current// vertex is already present in pathstatic bool isNotVisited(int x, List<int> path){ int size = path.Count; for(int i = 0; i < size; i++) if (path[i] == x) return false; return true;}// Utility function for finding paths in graph// from source to destinationprivate static void findpaths(List<List<int> > g, int src, int dst, int v){ // Create a queue which stores // the paths Queue<List<int> > queue = new Queue<List<int>>(); // Path vector to store the current path List<int> path = new List<int>(); path.Add(src); queue.Enqueue(path); while (queue.Count!=0) { path = queue.Dequeue(); int last = path[path.Count - 1]; // If last vertex is the desired destination // then print the path if (last == dst) { printPath(path); } // Traverse to all the nodes connected to // current vertex and push new path to queue List<int> lastNode = g[last]; for(int i = 0; i < lastNode.Count; i++) { if (isNotVisited(lastNode[i], path)) { List<int> newpath = new List<int>(path); newpath.Add(lastNode[i]); queue.Enqueue(newpath); } } }}// Driver codepublic static void Main(String[] args){ List<List<int> > g = new List<List<int>>(); int v = 4; for(int i = 0; i < 4; i++) { g.Add(new List<int>()); } // Construct a graph g[0].Add(3); g[0].Add(1); g[0].Add(2); g[1].Add(3); g[2].Add(0); g[2].Add(1); int src = 2, dst = 3; Console.WriteLine("path from src " + src + " to dst " + dst + " are "); // Function for finding the paths findpaths(g, src, dst, v);}}// This code is contributed by shikhasingrajput |
Javascript
// JavaScript code to print all paths of // source to destination in given graph// Utility function for printing// the found path in graphfunction printpath(path) { let size = path.length; for (let i = 0; i < size; i++) { process.stdout.write(path[i] + " "); } console.log();}// Utility function to check if current// vertex is already present in pathfunction isNotVisited(x, path) { let size = path.length; for (let i = 0; i < size; i++) { if (path[i] === x) { return 0; } } return 1;}// Utility function for finding paths in graph// from source to destinationfunction findpaths(g, src, dst, v) { // Create a queue which stores // the paths let q = []; // Path array to store the current path let path = []; path.push(src); q.push(path.slice()); while (q.length) { path = q.shift(); let last = path[path.length - 1]; // If last vertex is the desired destination // then print the path if (last === dst) { printpath(path); } // Traverse to all the nodes connected to // current vertex and push new path to queue for (let i = 0; i < g[last].length; i++) { if (isNotVisited(g[last][i], path)) { let newpath = path.slice(); newpath.push(g[last][i]); q.push(newpath); } } }}// Driver code // Number of vertices let v = 4; let g = Array.from({ length: 4 }, () => []); // Construct a graph g[0].push(3); g[0].push(1); g[0].push(2); g[1].push(3); g[2].push(0); g[2].push(1); let src = 2; let dst = 3; console.log(`path from src ${src} to dst ${dst} are`); // Function for finding the paths findpaths(g, src, dst, v); |
Output
path from src 2 to dst 3 are 2 0 3 2 1 3 2 0 1 3
Time Complexity: O(VV), the time complexity is exponential. From each vertex there are v vertices that can be visited from current vertex.
Auxiliary space: O(VV), as there can be VV paths possible in the worst case.
This article is contributed by Mandeep Singh. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
