java - minimum spanning tree out of adjacency matrix

Question

I have a problem that I am really struggling with. I have a set of points with weighed edges and I need to create a minimum spanning tree to find the shortest amount of edges needed. I need to do it in java. Right now I have it creating an adjacency matrix and thats the point im stuck. I really have no idea where to go next. Any help would be awesome.

Answer 1

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

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

Answer 2

如果您试图找到最小生成树，您将始终拥有相同数量的边，权重会有所不同。我推荐用来解决这个问题的方法是 Prim 算法。当您有明显的加权边缘时，它最有效。尽管其他人已经将其作为一种可能性进行了讨论，但我将在此处对其进行全面解释，以使用无向连通图解决最小生成树问题。

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