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

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