构造可以使n个城市连接的最小生成树

《构造可以使n个城市连接的最小生成树》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、西北农林科技大学信息工程学院C语言与数据结构实习报告题目：构造可以使n个城市连接的最小生成树学号2009012841姓名孙千翱专业班级信管091班指导教师王娟勤唐晶磊实践日期2010年7月19日-7月30日14目录一、综合训练目的与要求3二、综合训练任务3三、总体设计4四、详细设计说明4五、调试与测试6六、实习日志8七、实习总结9八、附录：核心代码清单914一、综合训练目的与要求按照数据结构、C程序设计教学计划的安排，7月19日到30日，开展为期两周的数据结构与C程序设计课程设计。该课程设计是数据结构、

2、C语言程序设计课程的重要实践教学环节，是一次全面的系统分析与设计能力的培养，是实现该专业学生总体培养目标的重要教学环节。使学生通过了解学科领域的发展动向，培养数据结构与程序设计的基本思想，独立分析和解决实践问题的能力，提高和锻炼学生动手能力。实习的基本要求(1)结合实践，学生选题与教师指定题目相结合，老师对题目的合理性、学生分组进行确认；(2)对所选题目，运用面向过程的分析与设计方法，给出系统分析与设计的结果，要求必须要运用数据结构课程中相关的基本知识；(3)选择熟悉的开发工具，用C语言完成系统实现和测

3、试，掌握系统实现和测试的方法，必须要有详尽的程序注释；(4)撰写开发文档，培养编写系统分析与设计文档的水平。二、综合训练任务主要任务：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。设计该程序的基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2、

4、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。三、总体设计《1》该程序的主要功能：能实现根据输入城市的信息可以判断该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。14《2》该城市间的距离网用邻接矩阵表示《3》用克鲁斯卡尔（Kruskal）算法建立最小生成树四、详细设计说明《1》该程序的主要功能：能实现根据输入城市的信息可以判断出该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通

5、过计算得到最小生成树的代价。该程序的模块结构功能图及主要函数如下：开始输入城市信息是否为连通图？求最小生成树初始化是否构成回路？将最小生成树边集合打印出最小生成树的权值与最小生成树的代价退出14a)intmain()//主程序b)intmenu()//菜单函数c)voidcreate()//输入城市信息函数d)voidjudge()//判断是否能够生成最小生成树函数e)voiddisplay()//打印输出f)voidset()//初始化pre[],rank[]函数g)voidfind()//判断是否构

6、成回路函数h)voidUnion()//将能构成最小生成树的边添加到一个集合l）voidKrushal()//克鲁斯算法求最小生成树《2》该城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图。用a[i][j]数组，利用邻接矩阵方式来储存城市与城市间信息。《3》算法设计（1）克鲁斯卡尔算法思想基本描述：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的

7、顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。（2）克鲁斯卡尔算法设计a.设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p[]中。b.从p[]中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。c.从E中删除此最小边，转b继续执行，直到k=n-1,算法结束d.判断是否构成回路的方法：设置集合S，其中存放已加入到生成

8、树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中或者两个顶点都不在S中，则不够成回路。14克鲁斯卡尔算法生成最小生成树的过程（3）防止不能构成最小生成树的图为避免输入的图构成的不是连通图，设计了judge()函数来判断输入数据构成的是否为连通图，此函数的主要算法是源于普里姆（PRIM）算法，经过改编，形成了新的函数。五、调试与测试211以一个