various ways and their runtime to check if a path exists between two nodes or vertices?

Question

I have seen articles in SO and elsewhere, where the following methods are cited for determining if a path exists between two nodes in a graph. I would like to know if any one is better than the other?

1. Breadth First Search - O(V + E)

2. Depth First Search - O(V + E)

3. Using disjoint sets - O(n log n) (not sure if it is O(n log n))

Does all these methods work for directed and undirected graphs, cyclic as well as acyclic?

Any preference for one over the other?

Answer 1

Well, I can definitely answer about linear time algorithms - BFS, DFS should work for all types of graphs (directed/undirected, cyclic/acyclic).
Think about it : starting with given node they will visit every edge and every node maximum once so they are not affected by cycle(s).
They will do it in a different fashion, BFS - "level-by-level", DFS - in a kinda greedy labyrinth-escaping manner, but they both will either terminate at some point (path exists), or after traversing all edges and visiting each node, they will terminate with negative result.
"Directivity" only affects what nodes are reachable from given node A, but implementation of algorithm(both bfs and dfs) is ignorant about whether graph directed or not.

I am not sure that union-find structure (your last item with disjoint sets) will help you in case of directed graphs.
Afaik, Union-find will put (merge) nodes a and b in one set if they are mutually reachable, i.e. there is a path from both a to b and vice versa.
If you have edge a -> b between a and b, and no other path leading from b to a, in that case according to Union-find data structure will not be able to put them not in one set.
, but obviously path a -> b exists.

Answer 2

BFS is better than DFS, as it finds the shortest path [so you can stop the algorithm quicker].

Do not know much about disjoint sets (will read about it shortly) and probably update my answer. [from what I read it seems to be more complicated than BFS, as it is used to find all components of the graph].

One of options not mentioned by you is to consider bidirectional BFS -- so running BFS from start and end simultaneously and stop once both searches meet. It will be inefficient though, if it is rather likely that no path exists and -- in case of cyclic graphs -- it could be implemented only if you keep references to both incoming and outgoing edges.

For sure: BFS and DFS work on undirected, directed, cyclic and acyclic.

If you want you can play with them a bit here.