查找图中所有不连通的子图

Question

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

Answer 1

我觉得你在找什么通常被称为颜色填充。这取决于你是否通过BFS或DFS遍历图形。

基本上你把未标记的（AKA无色）节点和分配一个新的标签到它。你同样的标签分配给邻近一个所有节点，依此类推到从该节点到达的所有节点。

当没有更多的可到达的节点可被标记，则通过拾取另一未标记的节点开始。请注意，这个新的节点未标记的事实意味着它是不是从我们前面的节点到达，因此在不同的断开组件。

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

Answer 2

不是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

更多信息此处。

Answer 3

这个问题有很多方面没有得到充分解释，所以我将给出一个比较详尽的答案。尽管我倾向于张贴文字墙。：/还要注意，我假设这是一个家庭作业问题或自学问题，所以我不会给出直接的答案。

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

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

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

此外，还有一个问题是“找到子图”（释义）是什么意思。通常图连接性是一个决策问题——简单地说“有一个连接的图”或“有两个或多个子图（又名，它是断开连接的）”。拥有一个算法需要最少的书本工作，这很好。:) 下一步是 数数 图表的数量，字面意思是图表的数量，而且书本工作也不错。最后，您可能需要每个子图中的节点列表。最后，您可能想要逐字复制子图、边和所有内容（因此返回类型将是图列表，我想，带有每个图都是连接的隐含不变量）。这些不同的结果类型都不需要不同的算法，但是 一定会 需要采用不同的方法来处理书籍工作。

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

Answer 4

JGraphT 是在LGPL牌照的漂亮的开源图形库。我已经在过去使用它来对付图表中的图形和检测周期。这也是相当容易使用，你可以使用 JGraph 以可视化的图表。

Answer 5

我假设你想找到所有的（强）连接的组件？对于可以使用的Tarjan算法（DFS的变体）

Answer 6

有关广度优先搜索，找到所有连接的节点是什么？一旦您已连接的节点列表，您可以从所有节点列表中减去这个名单。你最终断开的节点的列表

Answer 7

我跑进其中我想要的有向图的所有弱连接子图类似的问题。我的博客上讲述它这里。我使用的 JUNG 的API，并比较两种方法。我的第一种方法可以作为一个模板来解决你的问题。