蛮力法分析库卢卡尔关于最小生成树的算法设计分析.doc

蛮力法分析库卢卡尔关于最小生成树的算法设计分析.doc算法设计与分析实验报告三目内容:蛮力法分析库卢卡尔关于最小生成树的算法设计分析Prim算法和Kruskal算法卩rim算法逐次将最小权的边和相应顶点加到集合屮,适合于求边稠密的最小生成树;Kruskal算法先将所有边都放入集合,然后再逐个选择最小权的边,适合于求稀疏的网的最小生成树。根据克卢卡尔的最小生成树的算法,如上图己不能形成圈为前提,先把所有边放入一维数组屮,再对一维数组进行排序,选择权值最小的边。路径:v3->v2->v4->vl->v5 权值的和=1+3+2+9+4=19算法分析(伪代码):边:a[]={1,2,3,4,6,8,8,9,10,12)结点:u[]={vl,v2,v3,v4,v5)无向连通网为G二(V,E),令G的最小生成树为丁=(U,TE),其初始状态为U=V,TE={}T屮各顶点各自构成一个连通分量按照边的权值由小到大的顺序依次考察边集E屮的备条边。若被考察的边的两个顶点属于T的两个不同的连通分量,则将此边加入到TE屮去,同时把两个连通分量连接成一个连通分量;若被考察边的两个结点属于同一个连通分量,则舍去此边,以免造成I叫路,如此下去,当T中的连通分量个数为1时,:#include<>#include<>^defineM20ftdefineMAX20typedefstruct{intbegin;intend;intweight;ledge;typedefstruct{intadj;intweight;}AdjMatrix[MAX][MAX];typedefstruct{AdjMatrixarc;intvexnum,um;JMGraph;voidCreatGraph(MGraph*);voidsort(edge*,MG「aph*);voidMiniSpcinTree(MGraph*);intFind(int*,int);voidS\vapn(edge貧int,int);voidCreatGraph(MGraph*G){intij,n,m;printfC'请输入边数和顶点数:”);scanf(n%d%dH,&G->um,&G->vexnum);for(i=1;i<=G->vexnum;i++) {for(j=1;j<=G->vexnum;j++) {G->arc[i][=G->arc[jJ[i].adj=0; })for(i=1;i<=G->um;i++) {printf(u\n请输入有边的2个顶点”);scanf(n%d%dH,&n,&m);while(n<0IIn>G->vexnumIIm<0IIn>G->vexnum){printf(”输入的数字不符合要求请重新输入:”);scanf(”%d%d”,&n,&m);}G->arc[nJ[=G・>arc[m][n].adj=1;getchar();printf("\n请输入%d与%<1之间的权值:”,n,m); scanf("%d",&G->arc[n][m].weight);)printf("邻接矩阵为:\n");for(i=1;i<=G->vexnum;i++) {for(j=1;j<=G->vexnum;j++) {printf(n%dM,G->arc[i][j].