World's most popular travel blog for travel bloggers.

[Solved]: Why BFS is source vertex specific?

, , No Comments
Problem Detail: 

Take a graph $G=(V,E)$ .

As we know both DFS and BFS are graph search algorithms .

But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not connected to the source vertex $s$ but DFS takes care about all vertices in $V$.

I mean if $G$ has $l$ connected components and a vertex $s$ is in one of the connected component among $l$ , then if $s$ is the source vertex for BFS , then BFS performs only traversal on the only one connected component (which contains $s$).

If $G$ is input for BFS , it constructs one BFS tree (for component which contains $s$).

But in case of DFS , it constructs a DFS forest with $l$ DFS trees.

Why no BFS forest and it is restricted to a specifc component (containing $s$)? Any reason involved ?

For Bfs algorithm page # 595 and for Dfs algorithm page # 604 from here

Asked By : hanugm

Answered By : Yuval Filmus

Both BFS and DFS are algorithms for exploring a single connected component, and there are also several others. All such algorithms can be extended to explore all connected components in a graph.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29169

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback