Find if there is a path between two vertices in an undirected graph | Python3 program to check if there is exist a path between two vertices of an undirected graph . ; A BFS based function to check whether d is reachable from s . ; Base case ; Mark all the vertices as not visited ; Create a queue for BFS ; Mark the current node as visited and enqueue it ; Dequeue a vertex from queue and prit ; Get all adjacent vertices of the dequeued vertex s If a adjacent has not been visited , then mark it visited and enqueue it ; If this adjacent node is the destination node , then return true ; Else , continue to do BFS ; If BFS is complete without visiting d ; Driver program to test methods of graph class ; Create a graph given in the above diagram
from collections import deque NEW_LINE def addEdge ( v , w ) : NEW_LINE INDENT global adj NEW_LINE adj [ v ] . append ( w ) NEW_LINE adj [ w ] . append ( v ) NEW_LINE DEDENT def isReachable ( s , d ) : NEW_LINE INDENT if ( s == d ) : NEW_LINE INDENT return True NEW_LINE DEDENT visited = [ False for i in range ( V ) ] NEW_LINE queue = deque ( ) NEW_LINE visited [ s ] = True NEW_LINE queue . append ( s ) NEW_LINE while ( len ( queue ) > 0 ) : NEW_LINE INDENT s = queue . popleft ( ) NEW_LINE for i in adj [ s ] : NEW_LINE INDENT if ( i == d ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( not visited [ i ] ) : NEW_LINE INDENT visited [ i ] = True NEW_LINE queue . append ( i ) NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT V = 4 NEW_LINE adj = [ [ ] for i in range ( V + 1 ) ] NEW_LINE addEdge ( 0 , 1 ) NEW_LINE addEdge ( 0 , 2 ) NEW_LINE addEdge ( 1 , 2 ) NEW_LINE addEdge ( 2 , 0 ) NEW_LINE addEdge ( 2 , 3 ) NEW_LINE addEdge ( 3 , 3 ) NEW_LINE u , v = 1 , 3 NEW_LINE if ( isReachable ( u , v ) ) : NEW_LINE INDENT print ( " There ▁ is ▁ a ▁ path ▁ from " , u , " to " , v ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " There ▁ is ▁ no ▁ path ▁ from " , u , " to " , v ) NEW_LINE DEDENT DEDENT