java - 寻找具有超过 1 个连通分量的邻接矩阵的最小生成树

Question

我为我的一个项目构建了一个邻接矩阵，我需要能够从该矩阵中构建一个最小生成树。通过阅读，Prim 的算法似乎最适合这种情况，但是我们不能假设该图是一个大的连接组件，因为我知道我们必须处理的至少一个图有大约几千个连接的组件。Prim 的算法在这里仍然可行吗？如果可行，我还需要做些什么吗？

我在这里用Java编码，我可以很好地构造邻接矩阵，只是我卡在这部分。

Answer 1

所以你的意思是有可能没有生成树？在这种情况下 prims 很好，您只需要添加一个检查以确保所选列中存在可能的路径。在没有生成树的情况下，尝试用它做任何事情会很复杂，你必须删除你添加到树中的所有顶点，并将剩余部分视为新图。

编辑：如果您在矩阵（谷歌'D1 prims matrix'）上手动执行prims，那么很容易想象我所说的所选列中没有弧的意思。

Answer 2

除非图是连接的，否则没有最小生成树之类的东西。

因此，您可能想做以下两件事之一：要么构建所有连接组件的最小生成森林；要么 或者通过添加边来连接组件来为整个图形构建 MST。它是哪一个取决于您的问题域。

或者，也许您只是应该检测到图形未连接并表明它是不可能的？这很容易做到。