Print all paths from a given source to a destination using BFS
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 graph void 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 path int 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 destination void 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 program int 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 graph import java.io.*; import java.util.*; class Graph{ // utility function for printing // the found path in graph private 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 path private 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 destination private 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 code public 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 graph from typing import List from collections import deque # Utility function for printing # the found path in graph def 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 path def 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 destination def 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 code if __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 graph using System; using System.Collections.Generic; public class Graph{ // utility function for printing // the found path in graph static 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 path static 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 destination private 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 code public 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 graph function 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 path function 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 destination function 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.