I've looked for ways to count the no. of connected components online. I noticed that in most sites, the algorithm used is Depth-first search. I believe you can achieve the same thing Breadth-first search and union-find as well. So why do people prefer using DFS for finding number of connected components?
2 Answers
Mainly because of two reasons:
- It's simple and short. No data structure is required (well we need a stack but recursion takes care of that)
- It's memory friendly, Breath First Search has a memory complexity of
O(V)(Vis number of nodes). DFS on the other hand hasO(h)(his maximum depth of the recursion tree).
It is not better in terms of complexity, as in all cases you will visit a node exactly once. In terms of memory usage, you will always have to know what nodes were visited and what nodes were found and not visited yet. Depth-first will take a child node and visit its descendants before its siblings, while Breadth-first will visit the siblings before descendants. Depth-first is shorter and simpler and arguably more intuitive though, which could be the reason it is chosen in tutorials, books and presentation more frequently than the others.
In many cases the stack to be used is handled by recursion, but that is not necessarily a good idea, especially in the case of large graphs.
Related