克鲁斯卡尔算法c和c++ 实现代码

《克鲁斯卡尔算法c和c++ 实现代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、C的#include#include#include#defineMAX_NAME5#defineMAX_VERTEX_NUM20typedefcharVertex[MAX_NAME];/*顶点名字串*/typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/typedefstructMGraph/*定义图*/{Vertexvexs[MAX_VERTEX_NUM];AdjMatrixarcs;intve

2、xnum,arcnum;}MGraph;typedefstruct{Vertexadjvex;/*当前点*/intlowcost;/*代价*/}minside[MAX_VERTEX_NUM];intLocateVex(MGraphG,Vertexu)//定位{inti;for(i=0;i

3、网G的顶点数和边数(以空格为分隔)");scanf("%d%d",&G->vexnum,&G->arcnum);printf("请输入%d个顶点的值(<%d个字符):",G->vexnum,MAX_NAME);for(i=0;ivexnum;++i)/*构造顶点集*/scanf("%s",G->vexs[i]);for(i=0;ivexnum;++i)/*初始化邻接矩阵*/for(j=0;jvexnum;++j)G->arcs[i][j]=0x7fffffff;printf("请输入%d条边

4、的顶点1顶点2权值(以空格作为间隔):",G->arcnum);for(k=0;karcnum;++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[MAX_VERTEX_NUM],i,j;intk=0,a=0,b=0,min=G.arcs[a][b];for(i=0;i

5、+)set[i]=i;printf("最小代价生成树的各条边为:");while(k

6、if(set[i]==set[b])set[i]=set[a];}}}intmain(){MGraphg;CreateGraph(&g);kruskal(g);system("PAUSE");return0;}C++的#include#include#include#defineMAX_NAME5#defineMAX_VERTEX_NUM20typedefcharVertex[MAX_NAME];/*顶点名字串*/typedefintAdjMatrix[MAX_VE

7、RTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/structMGraph/*定义图*/{Vertexvexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;};//c++可以直接用结构体，不用申明typedefstruct{Vertexadjvex;/*当前点*/intlowcost;/*代价*/}minside[MAX_VERTEX_NUM];intLocateVex(MGraphG,Vertexu)//定位{inti;for(i=0;i

8、m;++i)if(strcmp(u,G.vexs[i])==0)returni;return-1;}voidCreateGraph(MGraph&G)//c++函数可以传地址做形参，c只能传指针{inti,j,k,w;Vertexva,vb;printf("请输入无向网G的顶点数和边数(以空格为分隔)