1 votes 1 votes Algorithms algorithms graph-algorithms test-series + – vaishali jhalani asked Dec 16, 2016 • retagged Jul 14, 2022 by makhdoom ghaya vaishali jhalani 1.4k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Kantikumar commented Dec 16, 2016 reply Follow Share 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 votes 0 votes vaishali jhalani commented Dec 16, 2016 reply Follow Share This should be different for directed and undirected graphs? 0 votes 0 votes Kantikumar commented Dec 16, 2016 reply Follow Share 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 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes Both BFS and DFS Arnab Bhadra answered Jun 17, 2017 Arnab Bhadra comment Share Follow See all 0 reply Please log in or register to add a comment.
