DFS on disconnected Graphs

Question

How does DFS(G,v) behaves for disconnected graphs ?

Suppose a graph has 3 connected components and DFS is applied on one of these 3 Connected components, then do we visit every component or just the on whose vertex DFS is applied.

Means Is it correct to say that

DFS on a graph having many components covers only 1 component.

I also tried online DFS visualization tools for disconnected graphs and they also support that it covers only 1 component. But still I want to confirm

• https://www.cs.usfca.edu/~galles/visualization/DFS.html
• https://visualgo.net/dfsbfs

Answer 1

Starting a search on a single component of a disconnected graph will search only that component; how could it be otherwise? There's no information to make a decision about when, how or where to move the search to a different component.

If you want to perform a complete search over a disconnected graph, you have two high level options:

• Spin up a separate search of each component, then add some logic to make a choice among multiple results (if necessary). This has the advantage of easy partitioning logic for running searches in parallel.
• Add logic to indicate how to combine the components into a "single" graph. Two ideas for this:
  • Add a dummy root node, and have the components be its children. This would be a neat workaround for tools which only cover one component, but you want to work with all three at once. It also means that if you're searching for a single best result, you're guaranteed to get the global best without any additional checks.
  • Put your components in a list and add logic that jumps to the next one when the search on the current completes. Add additional logic to compare multiple potential search results, if necessary.

Note that the same reasoning applies to breadth first searches as well.