How to Keep Track of Path in Bfs C++

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.

Attention reader! Don't stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course .

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

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

C++

#include <bits/stdc++.h>

using namespace std;

void printpath(vector< int >& path)

{

int size = path.size();

for ( int i = 0; i < size; i++)

cout << path[i] << " " ;

cout << endl;

}

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;

}

void findpaths(vector<vector< int > >&g, int src,

int dst, int v)

{

queue<vector< int > > q;

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 == dst)

printpath(path);

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);

}

}

}

}

int main()

{

vector<vector< int > > g;

int v = 4;

g.resize(4);

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" ;

findpaths(g, src, dst, v);

return 0;

}

Java

import java.io.*;

import java.util.*;

class Graph{

private static void printPath(List<Integer> path)

{

int size = path.size();

for (Integer v : path)

{

System.out.print(v + " " );

}

System.out.println();

}

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 ;

}

private static void findpaths(List<List<Integer> > g,

int src, int dst, int v)

{

Queue<List<Integer> > queue = new LinkedList<>();

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 == dst)

{

printPath(path);

}

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);

}

}

}

}

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<>());

}

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 " );

findpaths(g, src, dst, v);

}

}

Python3

from typing import List

from collections import deque

def printpath(path: List [ int ]) - > None :

size = len (path)

for i in range (size):

print (path[i], end = " " )

print ()

def isNotVisited(x: int , path: List [ int ]) - > int :

size = len (path)

for i in range (size):

if (path[i] = = x):

return 0

return 1

def findpaths(g: List [ List [ int ]], src: int ,

dst: int , v: int ) - > None :

q = deque()

path = []

path.append(src)

q.append(path.copy())

while q:

path = q.popleft()

last = path[ len (path) - 1 ]

if (last = = dst):

printpath(path)

for i in range ( len (g[last])):

if (isNotVisited(g[last][i], path)):

newpath = path.copy()

newpath.append(g[last][i])

q.append(newpath)

if __name__ = = "__main__" :

v = 4

g = [[] for _ in range ( 4 )]

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))

findpaths(g, src, dst, v)

Output:

path from src 2 to dst 3 are  2 0 3  2 1 3  2 0 1 3

This article is contributed by Mandeep Singh. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

How to Keep Track of Path in Bfs C++

Source: https://www.geeksforgeeks.org/print-paths-given-source-destination-using-bfs/

Share this post