All geek questions in one place

Compared to other algorithms, what makes depth search the best solution for counting the number of connected components in a graph?

I was looking for ways to say no. connected components online. I noticed that most sites use a depth search algorithm. I believe that you can achieve the same as searching in white and searching in union. So why do people prefer to use DFS to find the number of connected components?

+4
source share
2 answers

Mostly for two reasons:

  • It is simple and short. No data structure is required (we need a stack, but recursion will take care of this)
  • , Breath First Search O(V) (V - ). DFS, , O(h) (h - ).
+2

, node . , , . - node , Breadth-first . - , , , , , , .

, , .

+1

Source: https://habr.com/ru/post/1687110/

More articles:


All Articles