I want to find shortest path from node to some other node in Strongly Connected Component, the nodes could by chosen arbitrarily. Two searching methods come to mind Depth First Search or Breadth First Search.
Can be proven that for some situation is one preferable over the other?
One situation could be sparse graph vs. dense graph SCC.
0
votes
Do you have more information about the problem you're trying to solve? Are you just trying to locate a node or do you need a path (possibly shortest)? Is the node typically close or distant?
- ggorlen
Thank you, yes I meant shortes path from between two arbitrarily chosen nodes, no other info is given.
- world-r-u-ok
Then BFS is the way to go. DFS doesn't guarantee shortest path.
- ggorlen
2 Answers
0
votes
DFS does not guarantee that if node 1 is visited before another node 2 starting from a source vertex, then node 1 is closer to the source than node 2.
This can be easily seen from recursive nature of DFS. It visits the 'deeper' nodes or you can say farther from source nodes first. It goes as far as it can from the source vertex and then returns back to unvisited adjacent nodes of visited vertices.
On the other hand BFS always visits nodes in increasing order of their distance from the source. It first visits all nodes at same 'level' of the graph and then goes on to the next level.
Besides, the use of a non-recursive algorithm (BFS) is more productive purely in practical terms.
