Is DFS faster than BFS when searching a specific node in SSC?

Question

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.

Answer 1

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.

Answer 2

BFS visits all the nodes that are connected to the current node first, so each new node found is connected using the lowest number of edges possible. On the other hand, DFS follows one edge from each node until there are no edges to follow, not giving you the needed shortest path.