1 1 vote Given two vertices in a graph $s$ and $t$. Which of the two traversals (BFS and DFS) can be used to find if there is path from $s$ to $t$ ? Only BFS Only DFS Both BFS and DFS Neither BFS nor DFS Algorithms algorithms graph-algorithms test-series + – vaishali jhalani 2.3k views answer comment Share Follow Print See all 5 Comments 5 5 Comments reply Show 2 previous comments Kantikumar commented Dec 16, 2016 reply Follow flag We know that both BFS and DFS can be used to check whether a graph is connected or not. So if a graph is connected then we can say that there exist path from each vertex to every other vertex. If a graph is not connected, then we can find the connected components and if it happens that s and t are in two different components then we can say that there is no path between them. 0 0 replyShare vaishali jhalani commented Dec 16, 2016 reply Follow flag This should be different for directed and undirected graphs? 0 0 replyShare Kantikumar commented Dec 16, 2016 reply Follow flag This is always true for undirected graph. Coming to directed graph, these traversals will give strongly connected components. If s and t are in same strongly connected component then there is definitely a path. If they are not, then again we know that, Every directed graph is a DAG of its strongly connected components. Again apply traversal on this DAG and we can say whether path exists or not. Simple approach: Both DFS and BFS constructs traversal tree. Start traversing from s, if s and t are in same tree, there is path. This is true for both directed and undirected graphs. 1 1 replyShare Please log in or register to add a comment.
0 0 votes Both BFS and DFS Arnab Bhadra answered Jun 17, 2017 Arnab Bhadra comment Share Follow 0 reply Please log in or register to add a comment.
