Print all paths from a given source to a destination using BFS | Python3 program to print all paths of source to destination in given graph ; Utility function for printing the found path in graph ; Utility function to check if current vertex is already present in path ; Utility function for finding paths in graph from source to destination ; Create a queue which stores the paths ; Path vector to store the current path ; If last vertex is the desired destination then print the path ; Traverse to all the nodes connected to current vertex and push new path to queue ; Driver code ; Number of vertices ; Construct a graph ; Function for finding the paths
from typing import List NEW_LINE from collections import deque NEW_LINE def printpath ( path : List [ int ] ) -> None : NEW_LINE INDENT size = len ( path ) NEW_LINE for i in range ( size ) : NEW_LINE INDENT print ( path [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT def isNotVisited ( x : int , path : List [ int ] ) -> int : NEW_LINE INDENT size = len ( path ) NEW_LINE for i in range ( size ) : NEW_LINE INDENT if ( path [ i ] == x ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT return 1 NEW_LINE DEDENT def findpaths ( g : List [ List [ int ] ] , src : int , dst : int , v : int ) -> None : NEW_LINE INDENT q = deque ( ) NEW_LINE path = [ ] NEW_LINE path . append ( src ) NEW_LINE q . append ( path . copy ( ) ) NEW_LINE while q : NEW_LINE INDENT path = q . popleft ( ) NEW_LINE last = path [ len ( path ) - 1 ] NEW_LINE if ( last == dst ) : NEW_LINE INDENT printpath ( path ) NEW_LINE DEDENT for i in range ( len ( g [ last ] ) ) : NEW_LINE INDENT if ( isNotVisited ( g [ last ] [ i ] , path ) ) : NEW_LINE INDENT newpath = path . copy ( ) NEW_LINE newpath . append ( g [ last ] [ i ] ) NEW_LINE q . append ( newpath ) NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT v = 4 NEW_LINE g = [ [ ] for _ in range ( 4 ) ] NEW_LINE g [ 0 ] . append ( 3 ) NEW_LINE g [ 0 ] . append ( 1 ) NEW_LINE g [ 0 ] . append ( 2 ) NEW_LINE g [ 1 ] . append ( 3 ) NEW_LINE g [ 2 ] . append ( 0 ) NEW_LINE g [ 2 ] . append ( 1 ) NEW_LINE src = 2 NEW_LINE dst = 3 NEW_LINE print ( " path ▁ from ▁ src ▁ { } ▁ to ▁ dst ▁ { } ▁ are " . format ( src , dst ) ) NEW_LINE findpaths ( g , src , dst , v ) NEW_LINE DEDENT