资源描述：
《广工数据结构课程设计最小生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、课程设计课程名称数据结构学院专业班级学号学生姓名指导教师2015年7月2日1.需求分析题目：最小生成树问题若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。要求：（1）利用克鲁斯卡尔算法求网的最小生成树。（2）实现并查集。以此表示构造生成树过程中的连通分量。（3）以文本形式输出生成树中各条边以及他们的权值。输入的形式和输入值的范围：十进制数，0—100。输出的形式：十进制数。程序所能达到的功能：遍历所有城市生成最小生成树。测试数据：正确数据：城市个数3；3个城市的邻接矩阵：(1,
2、2,3;2,100,4;3,4,6)输出结果：第1条路段为1——2，权值为2第2条路段为1——3，权值为3遍历所有城市得到最小生成树的代价为：5错误数据：城市个数3；城市的邻接矩阵：(-2,5,1;3,0,1;3,2,1)输出结果：输入错误，请重新输入2.概要设计数据类型定义如下：typedefstructnode{intstr;/*起点*/intend;/*终点*/intdis;/*距离*/}node;nodep[max],temp;/*p记录城市信息*/intpre[100],rank[100];/*用于判断是否构成回路*/intn=0,arcs
3、[MAX_LNT][MAX_LNT];/*n表示城市个数，arcs[][]记录城市间权值*/主程序流程如下：3.详细设计（1）克鲁斯卡尔算法思想基本描述：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n 顶点而无边的非连通图T=(V,{ })，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。（2）克鲁斯卡尔算法设计：a. 设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排
4、序，存于p[ ]中。b. 从p[ ]中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。c. 从E中删除此最小边，转b继续执行，直到k=n-1, 算法结束 。判断是否回路：设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中 或者两个顶点都不在S中，则不够成回路。/*需要的函数声明*/int main ( ) //主
5、程序int menu ( ) //菜单函数void create ( ) //输入城市信息函数void judge ( ) //判断是否能够生成最小生成树函数void display( ) //打印输出void set ( ) //初始化pre[],rank[]函数void find ( ) //判断是否构成回路函数void Union ( ) //将能构成最小生成树的边添加到一个集合v
6、oid Krushal( ) //克鲁斯算法求最小生成树/*菜单函数*/intmenu(){intm;printf("..........................2015年7月2日......................");printf("求最小生成树");printf("________________________________");printf("1输入城市之间的信息");printf("2判断是否能构成一个最小生成树");printf("3遍历所有城市生成最小生成树");pri
7、ntf("0退出");printf("________________________________");printf("请输入所选功能0-3");scanf("%d",&m);if(m<0
8、
9、m>3)return4;returnm;}/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/voidset(intx)/*初始化*/{pre[x]=x;rank[x]=0;}/*找到这个点的祖先*/intfind(intx){if(x!=pre[x])pre[x]=find(pre[x]);returnpre[x];}/*将这两个
10、数添加到一个集合里去*/voidUnion(intx,inty){x=find(x);y=find(y);i
