52

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

4

8 回答 8

66

我认为您正在寻找的通常称为Flood Fill。是否通过 BFS 或 DFS 遍历图形取决于您。

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

当无法标记更多可达节点时，您可以通过选择另一个未标记节点重新开始。请注意，这个新节点未标记这一事实意味着它无法从我们之前的节点访问，因此位于另一个断开连接的组件中。

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

于 2009-08-28T19:50:15.417 回答
26

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

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph

d = list(nx.connected_components(g)) 
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

More information here.

于 2012-07-08T20:23:23.457 回答
12

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

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

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

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

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

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

于 2009-08-28T19:54:58.857 回答
3

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

于 2009-08-28T19:49:26.103 回答
2

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

于 2009-08-28T19:22:34.333 回答
2

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

于 2009-08-28T19:12:21.140 回答
1

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

于 2010-03-08T17:23:00.340 回答
1

我可能应该找到一个标准算法（维基百科有一些建议），但我自己想出了这个算法，它对我的​​目的很有效。我的 C# 实现需要几秒钟来处理具有 40,000 个节点和 44,000 条边的图，以找到 160 个子图和 20,000 个未连接的节点。我使用 HashSet 来存储每个子图组，因此测试组成员关系大约为 O(1)，整个算法变为 O(E*C)，其中 E 是边数，C 是图中的连通分量数. Wikipedia 提到了一个 O(N) 算法，它与节点数量呈线性关系，所以我确信我的算法效率不是最高的，但它对我的应用程序来说已经足够快了。（编辑：我也在掩饰合并组的成本，所以不要过分强调我的复杂性分析。）

逻辑：

For each edge A->B
  If A is in a group and B is not, add B to group A
  If A is not in a group and B is, add A to group B
  If A and B are in different groups, merge the groups
  If neither A or B is in a group, create new group containing A and B

伪代码：

graph = {nodes, edges}
groups = {}
foreach edge A->B in graph.edges:
    groupA = findgroup(A)
    groupB = findgroup(B)
    if (groupA && !groupB)
        groupA.add(B)
    elif (!groupA && groupB)
        groupB.add(A)
    elif (groupA && groupB)
        if (groupA != groupB)
            groupA.union(groupB)
            groups.delete(groupB)
    else
        groups.add({A,B})

findgroup(node):
    for group in groups:
        if group.contains(node):
            return group
    return null

请注意，这不会捕获任何未参与边缘的节点。对于我的特定目的，这很好。如果你想获得所有的单节点组，你可以做一个最后的传递：

foreach node in graph.nodes:
    group = findgroup(node)
    if !group:
        groups.add({node})
于 2022-02-12T03:33:32.310 回答