Menu
I have a graph which contains an unknown number of disconnected subgraphs. What's a good algorithm (or Java library) to find them all?
241
A graph is disconnected if at least two vertices of the graph are not connected by a path. If a graph G is disconnected, then every maximal connected subgraph of G is called a connected component of the graph G.
A graph G that is not connected has two or more connected components that are disjoint and have G as their union. Removing a cut vertex from a connected graph produces a subgraph that is disconnected.
A subgraph G′ = (V′, E′) of G is a graph with V′ ⊆ V and E ⊆ E1, where E1 is a subset of E, whose edges connect vertices that lie in V′. Clearly, G is a subgraph of itself. A subgraph G′ = (V′, E′) is connected if there exists at least one path connecting any pair of vertices in V′ (Figure 13.5c).
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.
134
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
