克鲁斯卡尔算法C和C++实现代码珍藏版本

April 17, 2021, 9:15 a.m. 文档页面

【文章导读】C的 #include #include #include #define MAX_NAME 5 #define MAX_VERTEX_NUM 20 typedef char VertexMAX_NAME;/*顶点名字串*/

文章介绍图片

  

【正文内容】

C的 #include<stdio.h> #include<stdlib.h> #include<string.h> #defineMAXNAME5 #defineMAXVERTEXNUM20 typedefcharVertex[MAXNAME];/*顶点名字串*/ typedefintAdjMatrix[MAXVERTEXNUM][MAXVERTEXNUM];/*邻接距阵*/ typedefstructMGraph/*定义图*/ { Vertexvexs[MAXVERTEXNUM]; AdjMatrixarcs; intvexnum。

arcnum; }MGraph; typedefstruct { Vertexadjvex;/*当前点*/ intlowcost;/*代价*/ }minside[MAXVERTEXNUM]; intLocateVex(MGraphG,Vertexu)//定位 { inti; for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)returni; return1; } voidCreateGraph(MGraph*G) { inti,j,k,w; Vertexva,vb; printf("请输入无向网G的顶点数和边数(以空格为分隔)\n"。

); scanf("%d%d",&G>vexnum,&G>arcnum); printf("请输入%d个顶点的值(<%d个字符):\n",G>vexnum,MAXNAME); for(i=0;i<G>vexnum;++i)/*构造顶点集*/ scanf("%s",G>vexs[i]); for(i=0;i<G>vexnum;++i)/*初始化邻接矩阵*/ for(j=0;j<G>vexnum;++j) G>arcs[i][j]=0x7fffffff。

printf("请输入%d条边的顶点1顶点2权值(以空格作为间隔):\n",G>arcnum); for(k=0;k<G>arcnum;++k) { scanf("%s%s%d%*c",va,vb,&w); i=LocateVex(*G,va); j=LocateVex(*G,vb); G>arcs[i][j]=G>arcs[j][i]=w;/*对称*/ } } voidkruskal(MGraphG) { intset[MAXVERTEXNUM],i,j; intk=0,a=0,b=0,

min=G.arcs[a][b]; for(i=0;i<G.vexnum;i++) set[i]=i; printf("最小代价生成树的各条边为:\n"); while(k<G.vexnum1) { for(i=0;i<G.vexnum;++i) for(j=i+1;j<G.vexnum;++j) if(G.arcs[i][j]<min) { min=G.arcs[i][j]; a=i; b=j; } min=G.arcs[a][b]=0x7fffffff; if(set[a]!=set[b]) { printf("。

%s%s\n",G.vexs[a],G.vexs[b]); k++; for(i=0;i<G.vexnum;i++) if(set[i]==set[b]) set[i]=set[a]; } } } intmain() { MGraphg; CreateGraph(&g); kruskal(g); system("PAUSE"); return0; } C++的 #include<stdio.h> #include<stdlib.h> #include<string.h> #defineMAXNAME5 #defineMAXVERTEXNUM20 typedefcharVertex[MAXNAME]。

/*顶点名字串*/ typedefintAdjMatrix[MAXVERTEXNUM][MAXVERTEXNUM];/*邻接距阵*/ structMGraph/*定义图*/ { Vertexvexs[MAXVERTEXNUM]; AdjMatrixarcs; intvexnum,arcnum; };//c++可以直接用结构体,不用申明 typedefstruct { Vertexadjvex;/*当前点*/ intlowcost;/*代价*/ }minside[MAXVERTEXNUM]; intLocateVex(MGraphG,Vertexu)//定位 { inti。

for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)returni; return1; } voidCreateGraph(MGraph&G)//c++函数可以传地址做形参,c只能传指针 { inti,j,k,w; Vertexva,vb; printf("请输入无向网G的顶点数和边数(以空格为分隔)\n"); scanf("%d%d",&G.vexnum,&G.arcnum); printf("请输入%d个顶点的值(<%d个字符):\n"。

G.vexnum,MAXNAME); for(i=0;i<G.vexnum;++i)/*构造顶点集*/ scanf("%s",G.vexs[i]); for(i=0;i<G.vexnum;++i)/*初始化邻接矩阵*/ for(j=0;j<G.vexnum;++j) G.arcs[i][j]=0x7fffffff; printf("请输入%d条边的顶点1顶点2权值(以空格作为间隔):\n",G.arcnum); for(k=0;k<G.arcnum;++k) { scanf("%s%s%d%*c"。

va,vb,&w); i=LocateVex(G,va); j=LocateVex(G,vb); G.arcs[i][j]=G.arcs[j][i]=w;/*对称*/ } } voidkruskal(MGraphG) { intset[MAXVERTEXNUM],i,j; intk=0,a=0,b=0,min=G.arcs[a][b]; for(i=0;i<G.vexnum;i++) set[i]=i; printf("最小代价生成树的各条边为:\n"); while(k<G.vexnum1) { for(i=0;i<G。

vexnum;++i) for(j=i+1;j<G.vexnum;++j) if(G.arcs[i][j]<min) { min=G.arcs[i][j]; a=i; b=j; } min=G.arcs[a][b]=0x7fffffff; if(set[a]!=set[b]) { printf("%s%s\n",G.vexs[a],G.vexs[b]); k++; for(i=0;i<G.vexnum;i++) if(set[i]==set[b]) set[i]=set[a]; } } } intmain() { MGraphg。

CreateGraph(g); kruskal(g); system("PAUSE"); return0; }

其他相关推荐  
三九文库 www.999doc.com
备案图标苏ICP备2020069977号