《克鲁斯卡尔算法C和C++实现代码.doc》由会员分享，可在线阅读，更多相关《克鲁斯卡尔算法C和C++实现代码.doc（4页珍藏版）》请在三一文库上搜索。
1、C的 #include #include #include #define MAX_NAME 5 #define MAX_VERTEX_NUM 20 typedef char VertexMAX_NAME;/*顶点名字串*/ typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接距阵*/ typedef struct MGraph/*定义图*/ Vertex vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; MGraph; typedef struct Vertex adjvex;
2、 /*当前点*/ int lowcost; /*代价*/ minsideMAX_VERTEX_NUM; int LocateVex(MGraph G,Vertex u)/定位 int i; for(i=0;ivexnum,&G-arcnum); printf(请输入%d个顶点的值(vexnum,MAX_NAME); for(i=0;ivexnum;+i) /* 构造顶点集*/ scanf(%s,G-vexsi); for(i=0;ivexnum;+i) /*初始化邻接矩阵*/ for(j=0;jvexnum;+j) G-arcsij=0x7fffffff; printf(请输入%d条边的顶点1
3、 顶点2 权值(以空格作为间隔): n,G-arcnum); for(k=0;karcnum;+k) scanf(%s%s%d%*c,va,vb,&w); i=LocateVex(*G,va); j=LocateVex(*G,vb); G-arcsij=G-arcsji=w; /*对称*/ void kruskal(MGraph G) int setMAX_VERTEX_NUM,i,j; int k=0,a=0,b=0,min=G.arcsab; for(i=0;iG.vexnum;i+) seti=i; printf(最小代价生成树的各条边为:n); while(kG.vexnum-1) f
4、or(i=0;iG.vexnum;+i) for(j=i+1;jG.vexnum;+j) if(G.arcsijmin) min=G.arcsij; a=i; b=j; min=G.arcsab=0x7fffffff; if(seta!=setb) printf(%s-%sn,G.vexsa,G.vexsb); k+; for(i=0;iG.vexnum;i+) if(seti=setb) seti=seta; int main() MGraph g; CreateGraph(&g); kruskal(g); system(PAUSE); return 0; C+的#include #incl
5、ude #include #define MAX_NAME 5 #define MAX_VERTEX_NUM 20 typedef char VertexMAX_NAME;/*顶点名字串*/ typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接距阵*/ struct MGraph/*定义图*/ Vertex vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; ; /c+可以直接用结构体，不用申明 typedef struct Vertex adjvex; /*当前点*/ int l
6、owcost; /*代价*/ minsideMAX_VERTEX_NUM; int LocateVex(MGraph G,Vertex u)/定位 int i; for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)return i; return -1; void CreateGraph(MGraph &G) /c+函数可以传地址做形参，c只能传指针 int i,j,k,w; Vertex va,vb; printf(请输入无向网G的顶点数和边数(以空格为分隔)n); scanf(%d %d,&G.vexnum,&G.arcnum); printf(请输入%
7、d个顶点的值(%d个字符):n,G.vexnum,MAX_NAME); for(i=0;iG.vexnum;+i) /* 构造顶点集*/ scanf(%s,G.vexsi); for(i=0;iG.vexnum;+i) /*初始化邻接矩阵*/ for(j=0;jG.vexnum;+j) G.arcsij=0x7fffffff; printf(请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): n,G.arcnum); for(k=0;kG.arcnum;+k) scanf(%s%s%d%*c,va,vb,&w); i=LocateVex(G,va); j=LocateVex(G,vb);
8、 G.arcsij=G.arcsji=w; /*对称*/ void kruskal(MGraph G) int setMAX_VERTEX_NUM,i,j; int k=0,a=0,b=0,min=G.arcsab; for(i=0;iG.vexnum;i+) seti=i; printf(最小代价生成树的各条边为:n); while(kG.vexnum-1) for(i=0;iG.vexnum;+i) for(j=i+1;jG.vexnum;+j) if(G.arcsijmin) min=G.arcsij; a=i; b=j; min=G.arcsab=0x7fffffff; if(seta!=setb) printf(%s-%sn,G.vexsa,G.vexsb); k+; for(i=0;iG.vexnum;i+) if(seti=setb) seti=seta; int main() MGraph g; CreateGraph(g); kruskal(g); system(PAUSE); return 0;