Find if there is a path between two vertices in an undirected graph | C ++ program to check if there is exist a path between two vertices of an undirected graph . ; function to add an edge to 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 print it ; 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 in the above diagram
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < int > > adj ; void addEdge ( int v , int w ) { adj [ v ] . push_back ( w ) ; adj [ w ] . push_back ( v ) ; } bool isReachable ( int s , int d ) { if ( s == d ) return true ; int n = ( int ) adj . size ( ) ; vector < bool > visited ( n , false ) ; queue < int > q ; visited [ s ] = true ; q . push ( s ) ; while ( ! q . empty ( ) ) { s = q . front ( ) ; q . pop ( ) ; for ( auto x : adj [ s ] ) { if ( x == d ) return true ; if ( ! visited [ x ] ) { visited [ x ] = true ; q . push ( x ) ; } } } return false ; } int main ( ) { int n = 4 ; adj = vector < vector < int > > ( n ) ; addEdge ( 0 , 1 ) ; addEdge ( 0 , 2 ) ; addEdge ( 1 , 2 ) ; addEdge ( 2 , 0 ) ; addEdge ( 2 , 3 ) ; addEdge ( 3 , 3 ) ; int u = 1 , v = 3 ; if ( isReachable ( u , v ) ) cout << " There is a path from " ▁ < < ▁ u ▁ < < ▁ " to " ▁ < < ▁ v ; STRNEWLINE TABSYMBOL else STRNEWLINE TABSYMBOL TABSYMBOL cout ▁ < < ▁ " There is no path from " ▁ < < ▁ u ▁ < < ▁ " to " return 0 ; }