查找所有断开子图的图 [英] Finding all disconnected subgraphs in a graph

问题描述

我有一个包含数量不明断开子图的曲线图。什么是好的算法（或Java库），以找到他们？

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

推荐答案

我觉得你在找什么通常被称为洪水填写。它是由你无论是通过BFS或DFS遍历图形。

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.

基本上，你需要一个未标记（AKA无色）节点，并分配一个新的标签给它。你相同的标号分配到邻近一个所有节点，依此类推到那些从该节点可到达的所有节点。

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.

这篇关于查找所有断开子图的图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！