图片抵千字，所以:
我的输入是左边的矩阵，我需要找到的是彼此相距最大一步(不是对角线)的节点集。上/下/左/右一步以上的节点将在一个单独的集合中。
因此，我的计划是从我找到的每个节点运行 BFS，然后返回它遍历的集合，并将其从原始集合中删除。重复这个过程，直到我完成。但后来我有了寻找图形分析工具的疯狂想法 - 我找到了 NetworkX。有没有一种简单的方法(算法？)可以在不手动编写 BFS 并遍历整个矩阵的情况下实现这一点？
谢谢
最佳答案
你正在尝试做的是搜索“连接的组件”和 NetworX 本身有一个方法可以做到这一点，正如在这个 documentation page 的第一个例子中所看到的那样。正如其他人已经在评论中指出的那样。
阅读你的问题，你的节点似乎在一个离散的网格上，你描述的连接概念与图像像素上使用的概念相同。
连通分量算法也可用于图形和图像。
如果性能对您来说很重要，我建议您使用连接组件的图像版本。 这是因为图像(像素网格)是一类特定的图形，因此处理节点网格的连通分量算法 是在知道图本身的拓扑结构的情况下构建的(即图是平面的，最大顶点度数是四)。图的通用算法必须能够处理通用图 (即它们可能不是平面的，某些节点之间有多个边)因此它必须花费更多的工作，因为它不能对输入图的属性做出太多假设。
由于可以在线性时间内在图表上找到连通分量，所以我并不是说图像版本会快几个数量级。两者之间只会有一个常数因子。 出于这个原因，您还应该考虑保存输入数据的数据结构是什么，以及将花费多少时间来创建每个版本的算法所需的输入结构。
关于python - 查找孤立子集的正确算法是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38277491/