克鲁斯卡尔算法实现最小耗费生成树

"最小耗费生成树的克鲁斯卡尔算法实现及实验报告" 最小耗费生成树是图论中的一个重要概念，用于寻找一个无向图的边集合，这些边连接所有顶点，且总权重尽可能小，形成的树被称为最小耗费生成树。克鲁斯卡尔(Kruskal)算法是一种典型的贪心算法，用于解决这个问题。该算法按照边的权重非降序排序，然后逐步选择边，每次选择不形成环的边加入到生成树中，直至所有顶点被连接。 克鲁斯卡尔算法的基本步骤如下： 1. **输入**: 给定一个含权连通无向图G=(V,E)，其中V是顶点集，E是边集。 2. **排序**: 按照边的权重对边集E进行非降序排序。 3. **初始化**: 对每个顶点v∈V，执行MAKESET操作，将顶点分入不同的集合，表示它们不属于同一棵树。 4. **构建树**: 初始化生成树T为空。 5. **循环**: 当T中的边数量少于n-1（n为顶点数量）时，执行以下步骤： - 选择E中权重最小的未选边（x, y）。 - 使用FIND操作检查x和y是否属于同一集合，即它们是否已经通过其他边连接。如果不在同一集合，则将边(x, y)添加到T，并使用UNION操作将x和y所在的集合合并，表示它们现在属于同一棵树。 6. **结束**: 当T中有n-1条边时，停止循环，生成树T即为最小耗费生成树。 在实际编程实现中，可以使用C或C++语言。在实验报告中，作者遇到了边排序和查找父节点的问题，这些问题通过使用库函数`qsort()`解决了。实验结果显示，通过克鲁斯卡尔算法成功构造了最小耗费生成树，并学会了如何将图问题抽象为函数，以及如何实现图的操作，如查找父节点、按权重排序边和顶点定位等。 此外，实验还涉及了一个贪心算法解决的选做问题，即给定一个正整数n和s，找到一种删除s个数字的策略，使得剩下的数字组成的新数最小。这个问题同样可以通过贪心策略来解决，但具体实现并未在报告中详述。 通过这个实验，作者加深了对贪心算法的理解，特别是其在最小耗费生成树问题中的应用，以及如何将图论问题转化为可编程的解决方案。