Kruskal算法求无向连通图最小生成树权重和

无向连通图最小生成树是一种在图论中用于求解连通图中最优路径的问题，特别在算法设计中被广泛应用，如在ACM竞赛中的数据结构与算法题目。在这个问题中，给定一个无向连通图，其特点是每个顶点之间有且仅有一条边，且每条边都有一个权重。目标是找到一棵包含所有顶点的最小生成树，使得树中所有边的权重之和最小。 算法的核心是Kruskal's Algorithm（克鲁斯卡尔算法），这是一种基于贪心策略的算法，用于寻找无向图的最小生成树。以下是算法的主要步骤： 1. 初始化：首先，创建一个数组`father[]`，其中`father[i]`表示顶点i的父节点，初始时每个顶点都是自己的父节点，即`father[i]=i`。 2. 边的排序：将边按照权重从小到大进行排序，这里使用了`compare`函数，如果边的权重相同，则根据起点较小的原则进行排序。这一步是为了确保在选择边时总是优先选择权重较低的边。 3. 遍历边：从排序后的边集合中依次选取边。对于每一条边，检查它的两个端点是否属于同一个连通分量。若不属于，则合并这两个连通分量（通过更新它们的父节点）并将该边的权重加入到最小生成树的总和中。 4. 终止条件：当所有顶点都包含在同一个连通分量中时，或者添加的边使图变为连通后不再添加新的边，算法结束。此时，剩下的连通分量就是最小生成树。 在提供的C++代码中，`kruskal()`函数实现了上述过程。首先调用`init()`函数对`father[]`进行初始化，然后调用`sort()`函数对边进行排序，接着通过`for`循环执行上述操作，最后输出最小生成树的权重之和。 在样例输入中，图有6个顶点和10条边，权重分别为15的边最终被选入最小生成树。因此，最小生成树的权重之和为15。整个程序通过读取输入的顶点数、边数以及边的权重，执行Kruskal算法，并返回最小生成树的权重总和。 总结来说，无向连通图最小生成树问题涉及图论中的基础概念，主要依赖于Kruskal算法来解决，适用于需要快速找到最小成本连接所有顶点的场景，例如网络设计、路由优化等问题。在编程实现中，需要理解如何处理连通性判断、边的排序以及如何合并连通分量以求得最优解。