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

算法设计与分析实验报告三818V4V1V5V3V2691012234题目内容:蛮力法分析库卢卡尔关于最小生成树的算法设计分析Prim算法和Kruskal算法Prim算法逐次将最小权的边和相应顶点加到集合中,适合于求边稠密的最小生成树;Kruskal算法先将所有边都放入集合,然后再逐个选择最小权的边,适合于求稀疏的网的最小生成树。根据克卢卡尔的最小生成树的算法,如上图已不能形成圈为前提,先把所有边放入一维数组中,再对一维数组进行排序,选择权值最小的边。路径:v3->v2->v4->v1->v5权值的和=1+3+2+9+4=19算法分析(伪代码)::a[]={1,2,3,4,6,8,8,9,10,12}结点:u[]={v1,v2,v3,v4,v5}=(V,E),令G的最小生成树为T=(U,TE),其初始状态为U=V,TE={}。若被考察的边的两个顶点属于T的两个不同的连通分量,则将此边加入到TE中去,同时把两个连通分量连接成一个连通分量;若被考察边的两个结点属于同一个连通分量,则舍去此边,以免造成回路,如此下去,当T中的连通分量个数为1时,:#include<> #include<> #define M 20 #define MAX 20 typedef struct { int begin; int end; int weight; }edge; typedef struct {int adj; int weight;  }AdjMatrix[MAX][MAX]; typedef struct {  AdjMatrix arc;intvexnum,um;}MGraph;voidCreatGraph(MGraph*);voidsort(edge*,MGraph*);voidMiniSpanTree(MGraph*);intFind(int*,int);voidSwapn(edge*,int,int);voidCreatGraph(MGraph*G){inti,j,n,m;printf("请输入边数和顶点数:");scanf("%d%d",&G->um,&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->um;i++){printf("\n请输入有边的2个顶点");scanf("%d%d",&n,&m);while(n<0||n>G->vexnum||m<0||n>G->vexnum){printf("输入的数字不符合要求请重新输入:");scanf("%d%d",&n,&m);}G->arc[n][m].adj=G->arc[m][n].adj=1;getchar();printf("\n请输入%d与%d之间的权值:",n,m);scanf("%d",&G->arc[n][m].weight);}printf("邻接矩阵为:\n");for(i=1;i<=G->vexnum;i++){f