Java 查找图中所有断开的子图

Finding all disconnected subgraphs in a graph

提问by Ollie Glass

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

我有一个图，其中包含未知数量的断开子图。找到它们的好算法（或 Java 库）是什么？

采纳答案by MAK

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.

我认为您正在寻找的通常称为Flood Fill。是通过 BFS 还是 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.

基本上，您采用一个未标记（AKA 未着色）节点并为其分配一个新标签。您为与该节点相邻的所有节点分配相同的标签，并为从该节点可到达的所有节点分配相同的标签。

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.

当没有更多未标记的节点时，您必须使用的不同标签的数量就是图形的组件数量。每个节点的标签告诉您哪个节点是哪个组件的一部分。

回答by oggy

I'm assuming you want to find all the (strongly) connected components? For that you can use Tarjan's algorithm(a variant of DFS)

我假设您想找到所有（强）连接的组件？为此，您可以使用Tarjan 算法（DFS 的变体）

回答by MedicineMan

What about a breadth first search to find all connected nodes? Once you have the list of connected nodes, you subtract this list from the list of all nodes. You end up with a list of disconnected nodes

广度优先搜索找到所有连接的节点怎么样？获得连接节点列表后，您可以从所有节点列表中减去此列表。您最终会得到一个断开连接的节点列表

回答by aperkins

JGraphTis a nice open source graphing library licensed under the LGPL license. I have used it in the past to deal with graphs and detecting cycles within the graphs. It is also fairly easy to use, and you can use JGraphto visualize the graphs.

JGraphT是一个很好的开源图形库，在 LGPL 许可下获得许可。我过去曾用它来处理图形和检测图形中的循环。它也相当容易使用，您可以使用JGraph来可视化图形。

回答by agorenst

There are many facets of this question that are not fully explained, so I'm going to give a somewhat exhaustive answer. My tendency to post walls-of-text notwithstanding. :/ Note also that I'm assuming this is a homework question or self-education question, so I'm not going to give a straight-up answer.

这个问题有很多方面没有完全解释，所以我将给出一个有点详尽的答案。尽管我倾向于张贴文本墙。:/ 另请注意，我假设这是一个家庭作业问题或自学问题，因此我不会直接给出答案。

The two basic algorithms for detecting connectivity of a graph is Depth First Searchand Breadth First Search. Those are really the 2 starting points you want to look at. Both will get you to the solution, but in different ways, and its hard to argue which is "better" without considering some pretty in-depth aspects of the problem. But let's move on.

检测图连通性的两种基本算法是深度优先搜索和广度优先搜索。这些确实是您想要查看的两个起点。两者都会让你找到解决方案，但方式不同，如果不考虑问题的一些非常深入的方面，很难争论哪个“更好”。但是让我们继续。

As I mentioned before, you left out some important details, and I'll touch upon some possibilities here.

正如我之前提到的，你遗漏了一些重要的细节，我将在这里谈一些可能性。

Is your graph directed or undirected? and do you consider connectivity in the "strong" sense (in which case, see oggy's answer), or connectivity in the "weak" sense? Depending on your answer, you will have to approach your algorithm in a subtly different way. Note that, for an undirected graph, weak and strong connectivity are equivalent, so that's nice. But you'll have to keep the structure of the graph in mind regardless, while implementing or finding an algorithm.

你的图是有向图还是无向图？您是否考虑“强”意义上的连通性（在这种情况下，请参阅 oggy 的答案），还是“弱”意义上的连通性？根据您的答案，您将不得不以一种略有不同的方式来处理您的算法。请注意，对于无向图，弱连通性和强连通性是等价的，这很好。但是无论如何，在实现或查找算法时，您都必须牢记图形的结构。

Furthermore, there is the question of what you mean by "finding the subgraphs" (paraphrase). Usually graph connectivity is a decision problem -- simply "there is one connected graph" or "there are two or more sub-graphs (aka, it's disconnected)". Having an algorithm for that requires the least amount of bookwork, which is nice. :) The next step up would be the countof graphs, literally the number of them, and that bookwork is also not so bad. Penultimately, you may want a list of nodes in each sub-graph. Lastly, you may want to literally copy out the sub-graphs, edges and all (so the return type would be a list of graphs, I suppose, with an implied invariant that each graph is connected). None of these different result-types would require a different algorithm, but will certainlyrequire a different approach to the bookwork.

此外，还有一个问题是“找到子图”（释义）是什么意思。通常图连通性是一个决策问题——简单地说就是“有一个连通图”或“有两个或更多子图（也就是断开的）”。拥有一个算法需要最少的书本工作，这很好。:)下一步行动将是数图表，它们的字面数量，以及bookwork也没有那么糟糕。最后，您可能需要每个子图中的节点列表。最后，您可能想要逐字复制子图、边和所有（因此返回类型将是一个图列表，我想，每个图都有一个隐含的不变量）。这些不同的结果类型都不需要不同的算法，需要对书本工作采取不同的方法。

All of this may seem like a ridiculous amount of overkill for what is a pretty basic question, but I thought I'd just highlight all of the aspects involved in even such a simple graph question. As a sort of cliffhanger, note how none of this even yet touches upon runtime or memory usage! :) - Agor

对于一个非常基本的问题来说，所有这些似乎都是荒谬的矫枉过正，但我​​想我只想强调即使是这样一个简单的图形问题所涉及的所有方面。作为一种悬念，请注意这些甚至还没有涉及运行时或内存使用！:) - 阿戈尔

回答by harschware

I ran into a similar problem where I wanted all the weakly connected subgraphs of a directed graph. I blogged about it here. I used the JUNGAPI and compare two approaches. My first approach could be used as a template to solve your problem.

我遇到了一个类似的问题，我想要一个有向图的所有弱连接子图。我在这里写了关于它的博客。我使用了JUNGAPI 并比较了两种方法。我的第一种方法可以用作解决您问题的模板。

回答by Datageek

Not a Java implementation but perhaps it will be useful for someone, here is how to do it in Python:

不是 Java 实现，但也许对某人有用，以下是在 Python 中的实现方法：

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph
d = list(nx.connected_component_subgraphs(g))
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

More information here.

更多信息在这里。