Is it correct that the result of BFS or DFS on a graph is a forest, not necessarily a tree?
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?