我有一个包含未知数量的不连通子图的图形。有什么好的算法（或Java库）可以找到它们全部吗？
8个回答
75
我认为你所需要的通常被称为Flood Fill。你可以选择使用BFS或DFS遍历图。
基本上，你会选择一个未标记（也就是未着色）的节点并将一个新标签分配给它。然后，将相邻的所有节点分配相同的标签，并继续分配直到所有可达节点都被标记。
当没有更多的可达节点可以标记时，你需要选择另一个未标记的节点重复上述过程。需要注意的是，这个新节点未标记意味着它无法从先前的节点到达，因此它属于不同的不连通组件。
当没有更多未标记的节点时，你所使用的不同标签数目就是该图中组件的数量。每个节点的标签告诉你该节点属于哪个组件。
- MAK
1
2谢谢，这是一个很好的起点和非常实用的答案。 - Ollie Glass
28
虽然不是Java实现，但或许对某些人有用。以下是在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
更多信息 在这里。
- Datageek
12
有许多问题的方面没有完全解释清楚，所以我将给出一个相当详尽的答案。尽管如此，我还是倾向于发布大量文本:/ 另请注意，我假设这是一个家庭作业问题或自学问题，因此我不会直接给出答案。
检测图的连通性的两种基本算法是深度优先搜索和广度优先搜索。这些算法都能帮助你找到答案，但它们的实现方式不同，在考虑一些相当深入的问题之前，很难说哪个更好。但我们继续吧。
正如我之前提到的，你遗漏了一些重要的细节，我在这里会提及一些可能性。
你的图是有向的还是无向的？你是否认为连通性在“强”意义上（如果是这种情况，请参见oggy的答案），还是在“弱”意义上？根据你的答案，你将不得不以微妙的不同方式来处理算法。请注意，对于无向图，弱连通性和强连通性是等价的，所以这很好。但你必须牢记图的结构，同时实现或查找算法。
此外，还有一个问题，就是“找到子图”这个概念的具体含义（换一种说法）。通常，图的连通性是一个决策问题——只需判断“是否存在一个连通图”或“是否存在两个以上的子图（也称为不连通）”。拥有一个算法，可以做到书本知识最少，这很好。接下来更进一步，则是需要计算图形数量，即字面意思上的数量，而这个书本上的工作也不是很麻烦。其次，您可能想要列出每个子图中的节点列表。最后，您可能想要复制所有子图，包括边缘等（因此返回类型将是一个图形列表，我想，其中隐含着每个图形都是连接的不变式）。这些不同的结果类型不需要不同的算法，但肯定需要不同的处理方法。这似乎对于一个基本的问题而言过分了，但我想强调即使是这样一个简单的图形问题，也牵扯到许多方面。作为一种悬念，注意，这些都还没有触及运行时间或内存使用率！ :) -Agor
检测图的连通性的两种基本算法是深度优先搜索和广度优先搜索。这些算法都能帮助你找到答案，但它们的实现方式不同，在考虑一些相当深入的问题之前，很难说哪个更好。但我们继续吧。
正如我之前提到的，你遗漏了一些重要的细节，我在这里会提及一些可能性。
你的图是有向的还是无向的？你是否认为连通性在“强”意义上（如果是这种情况，请参见oggy的答案），还是在“弱”意义上？根据你的答案，你将不得不以微妙的不同方式来处理算法。请注意，对于无向图，弱连通性和强连通性是等价的，所以这很好。但你必须牢记图的结构，同时实现或查找算法。
此外，还有一个问题，就是“找到子图”这个概念的具体含义（换一种说法）。通常，图的连通性是一个决策问题——只需判断“是否存在一个连通图”或“是否存在两个以上的子图（也称为不连通）”。拥有一个算法，可以做到书本知识最少，这很好。接下来更进一步，则是需要计算图形数量，即字面意思上的数量，而这个书本上的工作也不是很麻烦。其次，您可能想要列出每个子图中的节点列表。最后，您可能想要复制所有子图，包括边缘等（因此返回类型将是一个图形列表，我想，其中隐含着每个图形都是连接的不变式）。这些不同的结果类型不需要不同的算法，但肯定需要不同的处理方法。这似乎对于一个基本的问题而言过分了，但我想强调即使是这样一个简单的图形问题，也牵扯到许多方面。作为一种悬念，注意，这些都还没有触及运行时间或内存使用率！ :) -Agor
- agorenst
1
谢谢，这是一个自我学习的问题，我很感激您提供的详细信息，我很重视您揭示我所做的假设。我正在处理无向图，我的目标是编写一个方法，该方法接受一个图并返回所有子图的集合。 - Ollie Glass
2
尝试使用广度优先搜索来查找所有连接的节点？一旦您获得了连接节点的列表，您可以将该列表从所有节点的列表中减去。最终得到的是一个断开连接的节点列表。
- MedicineMan
1
哇，这正是我所需要的。如果您不关心特定子图分割等内容，它是最快的。唯一的问题是在图中从哪里开始搜索，但这取决于具体的图形。 - SumakuTension
2
我本应该找一个标准算法（Wikipedia上有一些建议），但我自己想出了这个方法，并且它在我的用途中表现良好。我的C#实现需要几秒钟来处理一个包含40,000个节点和44,000条边的图，以查找160个子图和20,000个未连接的节点。我使用了一个HashSet来存储每个子图组，因此测试组成员资格的时间复杂度约为O(1)，整个算法变为O(E*C)，其中E是边数，C是图中连接组件的数量。维基百科提到了一种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})
- yoyo
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接