用Prim算法求无向图的最小生成树 (2).pdf

Prim算法是一种用于寻找图中最小生成树的经典算法，特别适用于稠密图（边的数量接近于顶点数量的平方）。最小生成树是指一个无环且连通的子图，它包含原图的所有顶点，并且边的权重之和尽可能小。在Prim算法中，我们逐步构建这个子图，每次添加一条连接已选顶点和未选顶点的最小权重边。 在给定的代码中，首先定义了最大顶点数`maxver`和最大权值`maxright`，并使用二维数组`G`来表示邻接矩阵。用户通过输入指定图中的顶点数量和每对顶点之间的权值，如果两点间没有边，则权值设为`-1`，实际操作中通常用一个非常大的数来代替。代码中用`in[]`数组记录每个顶点是否已被加入到最小生成树中。 算法的主要部分是一个循环，首先从用户指定的起始顶点开始，然后不断寻找未被包含的顶点中与已包含顶点相连的最小权重边，将其添加到最小生成树中。这个过程通过遍历邻接矩阵`G`来完成，找到最小权重边后更新对应的`v1`和`v2`，以及它们在`in[]`数组的状态。当所有顶点都被包含或者无法找到满足条件的边时，循环结束。 值得注意的是，Prim算法的结果可能不唯一，这取决于选择起始顶点和每次添加边的选择顺序，但所有最小生成树的总权重是相同的。而Kruskal算法，与Prim算法不同，它对边进行排序并避免形成环路，因此在处理关节点（articulation point）的存在时可能会有不同的结果。 在代码中，`status`变量用于检查图是否连通，如果图不连通，程序会输出错误信息。程序打印出构建的最小生成树的边。 这段代码提供了一个简单的实现，但可能不适用于大规模图，因为它的时间复杂度是O(V^2)，其中V是顶点数量。对于稀疏图（边的数量远小于顶点数量的平方），可以考虑使用更高效的算法，如Kruskal算法或Floyd-Warshall算法的变体。此外，优化方法如优先队列（如二叉堆）可以显著提高Prim算法的性能，使其时间复杂度降低到O(E log V)，其中E是边的数量。