Finding all disconnected subgraphs in a graph

java algorithm graph disconnected subgraph
Ollie Glass picture Ollie Glass · Aug 28, 2009 · Viewed 30.4k times · Source

I have a graph which contains an unknown number of disconnected subgraphs. What's a good algorithm (or Java library) to find them all?

Answer

MAK picture MAK · Aug 28, 2009

I think what you are looking for is generally called a Flood Fill. It is up to you whether you traverse the graph through a BFS or a DFS.

Basically you take an unlabeled (AKA uncoloured) node and assign a new label to it. You assign the same label to all nodes adjacent to that one, and so on to all nodes that are reachable from that node.

When no more reachable nodes can be labeled, you start over by picking another unlabeled node. Notice that the fact that this new node is unlabeled implies that it is not reachable from our earlier node and is thus in a different disconnected component.

When there are no more unlabeled nodes, the number of distinct labels you had to use is the number of components of the graph. The label for each node tells you which node is part of which component.

Related questions

Good Java graph algorithm library?

Has anyone had good experiences with any Java libraries for Graph algorithms. I've tried JGraph and found it ok, and there are a lot of different ones in google. Are there any that people are actually using successfully in production …

Read More
Shortest path (fewest nodes) for unweighted graph

I'm trying build a method which returns the shortest path from one node to another in an unweighted graph. I considered the use of Dijkstra's but this seems a bit overkill since I only want one pair. Instead I have …

Read More
How to find if a graph has a cycle?

I know this question has been asked many times in this forum and everywhere else in the internet. But before you attack me with your claws outstretched please bear with me. I am a newbie learning graph. As part of …

Read More