0
$\begingroup$

Is it correct that the result of BFS or DFS on a graph is a forest, not necessarily a tree?

https://en.wikipedia.org/wiki/Graph_traversal#Graph_traversal_algorithms says

If each vertex in a graph is to be traversed by a tree-based algorithm (such as DFS or BFS), then the algorithm must be called at least once for each connected component of the graph. This is easily accomplished by iterating through all the vertices of the graph, performing the algorithm on each vertex that is still unvisited when examined.

For a undirected graph, is the DFS or BFS algorithm called exactly once for each connected component?

For a directed graph, is the DFS or BFS algorithm called at least once for each connected component?

  • What type of connectivity is used here for a directed graph? (weakly, strongly, or ...)
  • What kinds of "connected" components is the DFS or BFS algorithm called more than once for?

Thanks.

$\endgroup$
1
  • 1
    $\begingroup$ I don't think there is a clear answer unless we are told what algorithm is at issue. Depth first search (resp.breadth first search) is a strategy, and dictates the order in which nodes are visited but not the purpose of a visit. $\endgroup$
    – hardmath
    Jan 1 at 2:57
2
$\begingroup$

How many times you call DFS (or BFS) is a matter between you and DFS. What we can say is that in an undirected graph, either one of the searches done from a vertex $v$ explores the entire connected component of $v$, and nothing else. So you'd want to search from a vertex in each connected component, if you wanted to explore the entire graph.

(In particular, if you take the union of all the search trees, you get a spanning forest of the graph, with a spanning tree of each connected component.)

In a directed graph, doing a search from a vertex $v$ explores all the vertices reachable from $v$. This is not necessarily the same as a weakly connected or a strongly connected component. In general, the set of vertices reachable from $v$ is a union of multiple strongly connected components.

Tarjan's algorithm is a modification of DFS that finds the actual strongly connected components of a directed graph. Essentially, you pick a vertex $v$ and do a DFS from $v$, but do some extra book-keeping that lets you notice when you move to a different strongly connected component.

If $v$ can't reach all the vertices, then you might have to start over from a different vertex to get the rest. Alternatively and equivalently, you can add an artificial source vertex that has an edge to every other vertex, and do a single Tarjan-style DFS from there. (The artificial vertex will be its own strongly connected component, which we can disregard.)

$\endgroup$
4
  • $\begingroup$ Thanks. The wikipedia article says " the algorithm must be called at least once for each connected component of the graph", while your reply says "In general, the set of vertices reachable from 𝑣 is a union of multiple strongly connected components." Does your reply mean that DFS/BFS is called at most once for each strongly connected component of a directed graph? What does the Wikipedia article mean then? $\endgroup$
    – Tim
    Jan 5 at 3:44
  • $\begingroup$ When talking about connected components, the Wikipedia article presumably means an undirected graph, in which case everything is much more straightforward. $\endgroup$ Jan 5 at 4:25
  • $\begingroup$ For an undirected graph, isn't DFS/BFS called exactly once for each connected component? What does it mean by "at least once"? $\endgroup$
    – Tim
    Jan 5 at 12:20
  • $\begingroup$ Well, you can just call DFS/BFS on every vertex in order, because for most of them it will just say "that vertex has been visited" and stop, and then all you can say is that you're calling it "at least once" on each connected component. $\endgroup$ Jan 5 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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