2
$\begingroup$

I read BFS and DFS from CLRS and realized that the BFS algorithm does not consider graph with multiple connected components but only with single connected component, whereas DFS algorithm considers graph with multiple connected components as can be seen in below pic:

enter image description here

Are my observations correct? If yes, why is it like that? Is their any significance to it? Is their any reason for CLRS to give such algorithm or its perfectly acceptable to modify BFS to loop over all vertices, something similar to DFS in order to traverse all connected components of graph?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is not a fundamental difference. You can easily do BFS on a graph with multiple connected components by using the same loop as in lines 5-7 of the DFS procedure you show:

  • for each vertex $u \in G.V$:
    • if $u.\text{color} == \textsf{white}$:
      • BFS($G,u$)
Improve this answer
$\endgroup$
3
  • $\begingroup$ so at least my observation is correct that CLRS version of BFS does not work on graph with multiple connected components and there is nothing (logical / conceptual) harm in doing modification to BFS that you have suggested. I was wondering if CLRS had some unsaid reason behind giving BFS algorithm for graph with single connected component. But that does not seem to be the case. Please correct me if wrong. $\endgroup$
    – Rnj
    Jan 9, 2020 at 5:32
  • $\begingroup$ Also I was guessing if this will change time complexity of the algorithm. For adjacency list based implementation, it is $O(V+E)$. I believe this will remain unchanged as we check if $u.color==white$. Am I correct? $\endgroup$
    – Rnj
    Jan 9, 2020 at 5:46
  • $\begingroup$ Sorry, @Rnj, but I do not see your point. The implementation in CLRS guarantees to visit all nodes in the graph, of course, even if they are distributed in connected components. The implementation you show generates all the nodes adjacent to u which only in the first iteration is s. It will then unfold the entire graph by making u equal to one of the children of s and, from there, its adjacent nodes and so on ... $\endgroup$
    – Carlos Linares López
    Jan 9, 2020 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.