寻找孤立子集的正确算法是什么

Question

图片胜过千言万语，所以：

我的输入是左边的矩阵，我需要找到的是距离彼此最大一步（不是对角线）的节点集。多个上/下/左/右步距的节点将在一个单独的集中。你知道吗

所以，我的计划是从我找到的每个节点运行一个BFS，然后返回它遍历的集，并将其从原始集中移除。重复这个过程直到我完成。但后来我有了寻找图形分析工具的疯狂想法——我找到了NetworkX。有没有简单的方法（算法？）要实现这一点而不需要手动写入BFS，并遍历整个矩阵？你知道吗

谢谢

Answer 1

您要做的是搜索“连接的组件”和 NetworX本身就有一种方法可以做到这一点，正如其他人在评论中已经指出的那样，在这个documentation page的第一个示例中可以看到。你知道吗

阅读你的问题，你的节点似乎是在一个离散的网格和概念的连接，你所描述的是相同的用于像素的图像。你知道吗

连通分量算法可用于图形和图像。你知道吗

如果性能在你的情况下是重要的，我建议你去连接组件的图像版本。 这是因为图像（像素网格）是一类特殊的图形，因此连接组件算法处理节点网格 是在知道图本身的拓扑结构的情况下建立的（即图是平面的，最大顶点度是4）。图的一般算法必须能够处理一般图 （即它们可能不是平面的，在一些节点之间有多条边）因此它必须花费更多的工作，因为它不能对输入图的属性做太多假设。你知道吗

因为在线性时间内可以在图上找到连接的组件，所以我并不是说图像版本会快几个数量级。两者之间只有一个常数。 因此，您还应该考虑哪个数据结构保存您的输入数据，以及创建每个版本的算法所需的输入结构将花费多少时间。你知道吗