在图中查找所有断开连接的子图

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

这个问题有很多方面尚未完全解释,所以我将给出一个有点详尽的答案.尽管我倾向于发布文本墙.:/另请注意,我假设这是一个家庭作业问题或自我教育问题,所以我不打算直截了当地回答.

用于检测图的连通性的两种基本算法是深度优先搜索和广度优先搜索.这些确实是你想要看的2个起点.两者都会让你找到解决方案,但是以不同的方式,而且如果不考虑问题的一些非常深入的方面,很难说哪个是"更好".但让我们继续前进.

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

您的图表是针对还是未定向的？你是否认为"强"意义上的连通性(在这种情况下,参见oggy的答案),还是"弱"意义上的连通性？根据您的答案,您将不得不以微妙的方式接近您的算法.请注意,对于无向图,弱连接和强连接是等效的,所以这很好.但是,无论在实现或查找算法时,您都必须牢记图形的结构.

此外,还有一个问题是"查找子图"(释义)是什么意思.通常,图形连接是一个决策问题 - 简单地说"有一个连接图"或"有两个或更多个子图(又名,它已断开连接)".拥有一个算法需要最少量的书籍,这很好.:)下一步行动将是数图表,它们的字面数量,以及bookwork也没有那么糟糕.倒数第二,您可能需要每个子图中的节点列表.最后,您可能希望逐字地复制子图,边和所有(因此返回类型将是图表列表,我想,每个图都连接的隐含不变量).这些不同的结果类型都不需要不同的算法,但肯定需要采用不同的书本方法.

所有这些对于什么是一个非常基本的问题来说似乎是一种荒谬的过度杀戮,但我想我只是强调即使是这样一个简单的图形问题所涉及的所有方面.作为一种悬念,请注意这些甚至还没有触及运行时或内存使用!:) - Agor