离散数学--最小生成树实验报告.doc

《离散数学--最小生成树实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一、实验目的：掌握图的存储表示和以及图的最小生成树算法。二、实验内容：1.实现图的存储，并且读入图的内容。2.利用克鲁斯卡尔算法求网络的最小生成树。3.实现构造生成树过程中的连通分量抽象数据类型。4.以文本形式输出对应图的最小生成树各条边及权值。三、实验要求：1．在上机前写出全部源程序；2．能在机器上正确运行程序；3．用户界面友好。需求分析：1、利用克鲁斯卡尔算法求网的最小生成树；2、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列；3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩阵以及按权排序后的边和最后得到的最小生成树；克鲁斯卡尔算法：假设WN=

2、(V,{E})是一个含有n个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有n-1条边为止。测试数据：自行指定图进行运算四、详细设计源程序#include#include#defineM20#defineMAX20typedefstruct{intbegin;intend;intweight

3、;}edge;typedefstruct{intadj;intweight;}AdjMatrix[MAX][MAX];typedefstruct{AdjMatrixarc;intvexnum,arcnum;}MGraph;voidCreatGraph(MGraph*);voidsort(edge*,MGraph*);voidMiniSpanTree(MGraph*);intFind(int*,int);voidSwapn(edge*,int,int);voidCreatGraph(MGraph*G){inti,j,n,m;printf("请输入边数和顶点数:");scanf(

4、"%d%d",&G->arcnum,&G->vexnum);for(i=1;i<=G->vexnum;i++){for(j=1;j<=G->vexnum;j++){G->arc[i][j].adj=G->arc[j][i].adj=0;}}for(i=1;i<=G->arcnum;i++){printf("请输入有边的2个顶点");scanf("%d%d",&n,&m);while(n<0

5、

6、n>G->vexnum

7、

8、m<0

9、

10、n>G->vexnum){printf("输入的数字不符合要求请重新输入:");scanf("%d%d",&n,&m);}G->arc[n][m]

11、.adj=G->arc[m][n].adj=1;getchar();printf("请输入%d与%d之间的权值:",n,m);scanf("%d",&G->arc[n][m].weight);}printf("邻接矩阵为:");for(i=1;i<=G->vexnum;i++){for(j=1;j<=G->vexnum;j++){printf("%d",G->arc[i][j].adj);}printf("");}}voidsort(edgeedges[],MGraph*G){inti,j;for(i=1;iarcnum;i++){for(j=i+1;j<

12、=G->arcnum;j++){if(edges[i].weight>edges[j].weight){Swapn(edges,i,j);}}}printf("权排序之后的为:");for(i=1;iarcnum;i++){printf("<<%d,%d>>%d",edges[i].begin,edges[i].end,edges[i].weight);}}voidSwapn(edge*edges,inti,intj){inttemp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begi

13、n=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].weight;edges[i].weight=edges[j].weight;edges[j].weight=temp;}voidMiniSpanTree(MGraph*G){inti,j,n,m;intk=1;intparent[M];edgeedges[M];for(i=1;ivexnum;i++){for(j=i+1;j<=G