查找图中所有断开的子图 [英] 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.

基本上，您采用一个未标记(也称为未着色)节点并为其分配一个新标签.您为与该节点相邻的所有节点分配相同的标签，并为从该节点可到达的所有节点分配相同的标签.

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屋！