普里姆算法(prim)求最小生成树c程序

《普里姆算法(prim)求最小生成树c程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1程序测试用例如下：561425523463465程序运行过程截图：源程序清单如下：#include#definen6#defineMaxNum10000/*定义一个最大整数*//*定义邻接矩阵类型*/typedefintadjmatrix[n+1][n+1];/*0号单元没用*/typedefstruct{intfromvex,tovex;intweight;}Edge;typedefEdge*EdgeNode;intarcnum;/*边的个数*//*建立图的邻接矩阵*/voidCreatMatrix(adjmatri

2、xGA){inti,j,k,e;printf("图中有%d个顶点",n);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j){GA[i][j]=0;/*对角线的值置为0*/}else{GA[i][j]=MaxNum;/*其它位置的值置初始化为一个最大整数*/}}}printf("请输入边的个数：");scanf("%d",&arcnum);printf("请输入边的信息，按照起点，终点，权值的形式输入：");for(k=1;k<=arcnum;k++){scanf("%d,%d,%d",&i,

3、&j,&e);/*读入边的信息*/GA[i][j]=e;GA[j][i]=e;}}/*初始化图的边集数组*/voidInitEdge(EdgeNodeGE,intm){inti;for(i=1;i<=m;i++){GE[i].weight=0;}}/*根据图的邻接矩阵生成图的边集数组*/voidGetEdgeSet(adjmatrixGA,EdgeNodeGE){inti,j,k=1;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(GA[i][j]!=0&&GA[i][j]!=MaxNum){GE[k].

4、fromvex=i;GE[k].tovex=j;GE[k].weight=GA[i][j];k++;}}}}/*按升序排列图的边集数组*/voidSortEdge(EdgeNodeGE,intm){inti,j,k;Edgetemp;for(i=1;iGE[j].weight){k=j;}}if(k!=i){temp=GE[i];GE[i]=GE[k];GE[k]=temp;}}}/*利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树*

5、/voidPrim(adjmatrixGA,EdgeNodeT){inti,j,k,min,u,m,w;Edgetemp;/*给T赋初值，对应为v1依次到其余各顶点的边*/k=1;for(i=1;i<=n;i++){if(i!=1){T[k].fromvex=1;T[k].tovex=i;T[k].weight=GA[1][i];k++;}}/*进行n-1次循环，每次求出最小生成树中的第k条边*/for(k=1;k

6、=T[j].weight;m=j;}}/*把最短边对调到k-1下标位置*/temp=T[k];T[k]=T[m];T[m]=temp;/*把新加入最小生成树T中的顶点序号赋给j*/j=T[k].tovex;/*修改有关边，使T中到T外的每一个顶点保持一条到目前为止最短的边*/for(i=k+1;i

7、e){inti;printf("按照起点，终点，权值的形式输出的最小生成树为：");for(i=1;i<=e;i++){printf("%d,%d,%d",GE[i].fromvex,GE[i].tovex,GE[i].weight);}}voidmain(){adjmatrixGA;EdgeGE[n*(n-1)/2],T[n];CreatMatrix(GA);InitEdge(GE,arcnum);GetEdgeSet(GA,GE);SortEdge(GE,arcnum);Prim(GA,T);printf("");OutE

8、dge(T,n-1);}