1、 工学系课程设计报告工学系课程设计报告 设设 计计 题题 目：目：最小生成树最小生成树 系系 别：别： 专专 业业 ( (方方 向向) )： 年年 级、级、 班：班： 学学 生生 姓姓 名：名： 学学 生生 学学 号：号： 指指 导导 教教 师：师： 年 月日 目录目录 一、系统开发的背景一、系统开发的背景 1 二、系统分析与设计二、系统分析与设计 1 （一）（一） 系统功能要求系统功能要求 1 （二）（二） 系统模块结构设计系统模块结构设计 .1 三、系统的设计与实现三、系统的设计与实现 . 2 ( (一一) ) 输入城市信息：输入城市信息：CREATE CREATE ( ( ) ) .2
2、（二）（二） 判断是否能够生成最小生成树判断是否能够生成最小生成树：JUDGE( )JUDGE( ) 2 （三）（三） 求最小生成树：求最小生成树：KRUSKAL( )KRUSKAL( ) 3 四、系统测试四、系统测试 . 4 （一）（一） 测试测试INT MENU INT MENU ( ( ) )函数函数4 （二）（二） 测试测试VOID CREATE VOID CREATE ( ( ) )函数函数 4 （三）（三） 测试测试VOID JUDGEVOID JUDGE( ( ) )函数函数5 （四）（四） 测试测试VOID VOID K KRUSKALRUSKAL( ( ) )函数函数5 （五
3、）（五） 测试测试EXITEXIT( ( ) )函数函数.5 五、总结五、总结 6 六、附件（代码、图表）六、附件（代码、图表） . 6 1 最小生成树最小生成树 一、一、系统开发的系统开发的背景背景 为了在保证连通即可的 n 个城市之间建设网络，求出最经济的架设方 法，因此设计了这个程序。 二、系统二、系统分析与分析与设计设计 （一）（一） 系统功能要求系统功能要求 可以对给定的网和起点，用 PRIM 算法和 kruskal 算法的基本思想求解 出所有的最小生成树。存储结构可自行选择； （二）（二） 系统模块结构设计系统模块结构设计 通过对系统功能的分析，最小生成树功能如图 1 所示。 图
4、1 最小生成树功能图 通过上图的功能分析，把整个系统划分为 4 个模块： 1、 输入城市信息， 该模块主要实现： 输入城市的个数以及输入城市之 间的邻接矩阵，借助函数 create( )来实现； 2 2、 判断是否生成模块，该模块主要实现判断是否能够生成最小生成 树，借助函数 judge ( )来实现； 3、 求最小生成树模块，该模块主要实现显示所输入城市之间各路段 的权值，求出最小生成树，借助函数 Kruskal( )来实现； 4、 退出模块， 该模块主要实现终止正在执行的程序， 借助函数 exit( ) 来实现； 三、系统的设计三、系统的设计与实现与实现 ( (一一) ) 输入城市信息输入
5、城市信息：createcreate ( )( ) 分析：首先输入城市的基本信息。 该模块的具体代码如下所示： void create() int i,j; printf(“请输入城市的个数:n“); scanf(“%d“, printf(“输入%d 个城市的邻接矩阵:n“,n); for(i=1;i=100000000) printf(“不能构成最小生成树n“); else printf(“能构成最小生成树n“); （三）（三） 求最小生成树：求最小生成树：Kruskal( )Kruskal( ) 该模块的具体代码如下所示： void Kruskal() int ans=0,i,j,k=0;
6、int index; int count=0; for(i=1;i=ranky) prey=x; rankx+; else prey=x; void Kruskal() int ans=0,i,j,k=0; int index; int count=0; for(i=1;i=100000000) printf(“不能构成最小生成树n“); else printf(“能构成最小生成树n“); int main() while(1) switch(menu() case 1:create();break; case 2:judge();break; 10 开始 输入城市信息 是否为 连通 图？ 求最小生成树 初始化 是 否 构 成 回路？ 将最小生成树边
