Let G=(V, E) be an undirected graph. The connected components of G are the "pieces' of G. The goal is to compute all connected components. A good application for this is to check if a network is disconnected, or to see if everything in a graph can be reached from everything else.
To compute all components:
Mark all nodes unexplored
for i=1 to n
if i not yet explored
BFS(G, i)
The call to BFS discovers precisely i's connected component. This algorithm can't miss any nodes because it actually walks through every node so it must find every connected component. If we wanted to find the number of connected components, we could keep a count variable and increment it each time we call BFS.
No comments:
Post a Comment