最小生成树的课程设计

《最小生成树的课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法课程设计报告课程设计题目：构造可以使n个城市连接的最小生成树专业班级：信息与计算科学1001班姓名：学号：设计室号：理学院机房设计时间：2011-12-26批阅时间：指导教师：成绩：构造可以使n个城市连接的最小生成树主要任务：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。设计该程序的基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最

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

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

4、nion()//将能构成最小生成树的边添加到一个集合l）voidKrushal()//克鲁斯算法求最小生成树体会确定程序功能设计出总体流程对整个设计进行非常重要，明确要完成设计需要的程序算法，为整个设计流程划出大纲，可以使整个设计思路更加简单明了。《2》构造结构体本题为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。#definemax20#defineMAX_LNT10typedefstructnode/*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/{intstr;/*起点*/intend;/*终

5、点*/intdis;/*距离*/}node;nodep[max],temp;/*p记录城市信息*/intpre[100],rank[100];/*用于判断是否构成回路*/intn=0,arcs[MAX_LNT][MAX_LNT];/*n表示城市个数，arcs[][]记录城市间权值*/《3》初始化voidset(intx)/*初始化*/{pre[x]=x;rank[x]=0;}intfind(intx)/*找到这个点的祖先*/{if(x!=pre[x])pre[x]=find(pre[x]);returnpre[x];}voidUnion(i

6、ntx,inty)/*将这两个添加到一个集合里去*/{x=find(x);y=find(y);if(rank[x]>=rank[y]){pre[y]=x;rank[x]++;}elsepre[y]=x;}该城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图。用a[i][j]数组，利用邻接矩阵方式来储存城市与城市间信息。voidcreate()/*输入城市信息*/{inti,j;printf("请输入城市的个数:");scanf("%d",&n);printf("输入%d个城市的邻接矩阵:",n

7、);for(i=1;i<=n;i++){for(j=1;j<=n;j++)scanf("%d",&arcs[i][j]);}}《3》算法设计（1）克鲁斯卡尔算法思想基本描述：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。（2）克鲁斯卡尔算法设计a.设置计数器E，初值为0，记录已选中的边

8、数。将所有边从小到大排序，存于p[]中。b.从p[]中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1