graph-theorydepth-first-searchbreadth-first-searchconnected-components

Why can DFS handle a graph with multiple components while BFS cannot?


Consider the standard pseudocode for BFS (modified from CLRS)

def BFS(G, source):
  Initialize Boolean array visited to keep track of visited nodes
  Mark source as visited
  Add source to queue Q

  while Q is not empty:
    u = Q.dequeue()
    for v in G[u]:
      if v is not visited:
        mark v as visited and add to queue

This version of BFS runs on a starting vertex source and will visit all vertices reachable from source. Yet if G has multiple components, BFS() won't visit all the vertices in G. It therefore makes sense to me to have the function

def BFS_wrapper(G):
for source in G:
  if source not in visited:
    BFS(source)

which will enable BFS to reach all the vertices in the entire graph G, even if G has multiple components. Yet the standard pseudocode for BFS does not include this wrapper. Moreover, the standard pseudocode for DFS seems to always has this exact 'wrapper' function that let's DFS reach all the vertices in the entire graph G, even if G has multiple components.

My question is: why does the standard DFS code have this wrapper function while the standard BFS code does not? It seems like DFS is meant to be used on a graph with multiple components while BFS is only meant to be used on a graph with a single component. Equivalently, why does BFS seem like it is not meant to run on a graph with multiple components but DFS is?


Solution

  • Initializing the queue q with a vertex from each component allows BFS to simultaneously explore the different components. Thus, we don't need a 'wrapper' function to give BFS the ability to explore a graph with multiple components.