最小生成树问题实习报告题目：编制一个求最小生成树的程序班级：信管08-2：顾先：0801051409完成日期：2010.5.31一需求分析 1. 要在n个城市间建设通信网络只需要架设n-1条线路即可建立的最小生成树即能实现付出最低的经济代价2. 程序利用的是克鲁斯卡尔算法求网的最小生成树3.输出结果为文本形式的生成树和他们之间的权值4. 演示程序以用户和计算机对话的形式进行即在计

克鲁斯卡尔算法： ： 班级：信工0808 成绩：1原理由于克鲁斯卡尔算法是在图中从边长小的边开始查找为了减少重复查找与比较的次数直接使用快排使边长按非降序排列为了使所构成的最小生成树不出现回路则对顶点进行集合划定father[i]保存顶点i所在的集合序号初始时每个顶点对应的集合序号为其顶点序号只要两顶点ab不再同一集合内即可加入到最小生成树