邻接矩阵中的最小生成树

Question

我有一个问题，我真的很挣扎。我有一组带有加权边的点，我需要创建一个最小生成树来找到所需的最短边数。我需要在java中完成它。现在我有它创建一个邻接矩阵，这就是我陷入困境的一点。我真的不知道下一步该往哪里去。任何帮助都是极好的。

Answer 1

看看Kruskal和Prim算法，我真的很喜欢Prim，因为它很容易实现和理解：http://en.wikipedia.org/wiki/Prim%27s_algorithm

关于你的问题，接下来做什么（Resumed Prim的算法）：选择一个随机顶点并以较小的成本获得边缘，将其插入到MST中。虽然您的MST没有所有顶点：选择MST边缘成本较低的边缘并将其插入MST。

Answer 2

如果您要查找最小生成树，则始终具有相同数量的边，权重将不同。我建议用来解决这个问题的方法是Prim的算法。当您有不同的加权边时，它最有效。即使其他人已经讨论过它作为一种可能性，我将在这里完整地解释它以解决无向连通图的最小生成树问题。

Prim的第一步是从任何顶点V开始，并将其添加到一个名为“Discovered”的（当前）空顶点集中。从那里，您将查看与V相邻的所有边（使用您的邻接矩阵）并连接到不在“已发现”中的顶点（使用您的发现集），并将它们添加到最小堆结构。堆将允许您采用最小边缘并将其添加到新的树结构中。该边缘的另一端是您的下一个新起始顶点。重复此过程，直到获得最小生成树。