Disconnected node during Graph traversal

问题:

I have been going through Breadth First Traversal at this link
Breadth First Traversal

Now what if the graph structure is changed to this

The node 3 is now disconnected from the graph. When traversal program is now used, it does'nt display vertex 3. Is there a way where we can dispaly this vertex as well?

回答1:

To my understanding, BFS would keep looking for unvisited nodes as long as they exist; however, if this is not done, BFS only visits nodes in the connected component of the initial vertex. This seems to be more a matter of definition than an actual programming problem; simply restart the BFS implementation on unvisited nodes as long as they exist - if visiting of all connected components is desired.

回答2:

Many implementations of BFS/DFS assume implicitly that the graph is connected.

Is there a way where we can dispaly this vertex as well?

Yes there is. If after finishing BFS still there are some unvisited vertices, enqueue them into the queue.

回答3:

If you have a list of all nodes, your graph search algorithm of choice (DFS/BFS) will discover the connected components one at a time.

You could do this in the following way.

For example, consider your example graph in which there are 4 nodes and edges between 0, 2, 2, 0 and 1, 2 and node 3 has no incoming or outgoing edges.

You would have a list of nodes {0, 1, 2, 3}

And to discover all connected components, you would do the following:

Initialize visited array. Set all nodes to false

for node in list:
    if not visited: dfs(node)

where dfs is implemented in the usual way. Here when you run the code on our list {0,1,2,3}, the nodes {0,1,2} will be visited by the first dfs call and 0,1,2 will be marked visited. Then when we come across 3, since it is not visited, there will be another dfs call.

Hope you get the idea.