我为我的一个项目构建了一个邻接矩阵，并且我需要能够从该矩阵构建最小生成树。通过阅读，Prim 的算法似乎最适合这种情况，但是我们不能假设该图是一个大的连通分量，因为我知道一个事实，我们必须处理的至少一个图有大约数千个连接的组件。 Prim 的算法在这里仍然可行吗？如果可行，我需要做些什么额外的事情吗？
我在这里用Java编码，我可以很好地构建邻接矩阵，只是我卡在了这部分。
最佳答案
所以你的意思是有可能没有生成树？在这种情况下 prims 就可以了，您只需要添加一个检查来确定所选列中是否存在可能的路径。在没有生成树的情况下，尝试用它做任何事情都会很复杂，您必须删除添加到树中的所有顶点并将其余部分视为新图。
编辑:如果您在矩阵上手动执行 prims(谷歌“D1 prims 矩阵”)，那么很容易想象我所说的所选列中没有弧的意思。
关于java - 寻找具有超过 1 个连通分量的邻接矩阵的最小生成树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5885543/