Does BFS and DFS traversal sequence exist for disconnected graphs? Is yes can you please give a dry run of the algorithm on a disconnected graph?
Yes.
We start BFS or DFS on any random vertex (s) . Now BFS or DFS will print all the vertices which are reachable from s.
What about other vertices? The graph can be disconnected.
To handle this situation we can do a little bit of modification in our algorithm. We will use an array of size V(number of vertices). Whenever we will visit a vertex we will mark it as visited.
Our code will be like this:
For all the vertices v of G
{
if(visited[v] == false)
BFS(v) or DFS(v) // count++;
}
the count will give us the number of connected components.
