分别利用prim算法和kruskal算法实现求图的最小生成树

/*分别利用prim算法和kruskal算法实现求图的最小生成树*/#include#include#define MaxVertexNum 12#define MaxEdgeNum 20#define MaxValue 1000typedef int Vertextype;typedef int adjmatrixMaxVertexNumMaxVertexNum;typedef Vertextype vexlistMaxVertexNum;int visitedMaxVertexNum=0;struct edgeElemint fromvex;int endvex;int weight;typedef struct edgeElem edgesetMaxVertexNum;void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)int i,j,k,w;printf(输入%d个顶点数据,n);for(i=0;in;i+) scanf(%d,&GVi);for(i=0;in;i+) for(j=0;jn;j+) if(i=j) GAij=0; else GAij=MaxValue;printf(输入%d条无向带权边,e);for(k=0;ke;k+)scanf(%d%d%d,&i,&j,&w);GAij=GAji=w;void Creat_edgeset(vexlist GV,edgeset GE,int n,int e)int i,j,k,w;printf(输入%d个顶点数据,n);for(i=0;in;i+) scanf(%d,&GVi);printf(输入%d条无向带权边,e);for(k=0;ke;k+) scanf(%d%d%d,&i,&j,&w); GEk.fromvex=i; GEk.endvex=j; GEk.weight=w;void output_edgeset(edgeset GE,int e)int k;for(k=0;ke;k+)printf(%d %d %d,GEk.fromvex,GEk.endvex,GEk.weight);printf(n);void prim(adjmatrix GA,edgeset CT,int a,int n)int i,j,t,k,w,min,m;struct edgeElem x;for(i=0;in;i+)if(ia) CTi-1.fromvex=a; CTi-1.endvex=i; CTi-1.weight=GAai; for(k=1;kn;k+) min=MaxValue; m=k-1; for(j=k-1;jn-1;j+) if(CTj.weightmin)min=CTj.weight;m=j; x=CTk-1;CTk-1=CTm;CTm=x; j=CTk-1.endvex; for(i=k;in-1;i+)t=CTi.endvex;w=GAjt; if(wCTi.weight) CTi.weight=w; CTi.fromvex=j; void kruskal(edgeset GE,edgeset C,int n) int i,j,k,d; int m1,m2; adjmatrix s;for(i=0;in;i+) for(j=0;jn;j+) if(i=j) sij=1;else sij=0; k=1;d=0;while(kn) for(i=0;in;i+) if(siGEd.fromvex=1) m1=i; if(siGEd.endvex=1) m2=i;if(m1!=m2)Ck-1=GEd;k+;for(j=0;jn;j+)sm1j=sm1j|sm2j;sm2j=0;d+;void main()int n,e;vexlist GV;adjmatrix GA;edgeset GE,C;printf(输入图的顶点数和边数：);scanf(%d%d,&n,&e);Creat_adjmatrix( GV, GA, n, e);printf(利用prim算法从0点出发求图的最小生成树：n);prim(GA,GE,0,n);output_edgeset( GE, n-1);printf(输入图的顶点数和边数:);scanf(%d%d,&n,&e);Creat_edgeset( GV,GE,n, e);printf(利用kruskal算法从0点出发求图的最小生成树：n);kruskal( GE, C, n);output_edgeset( C, n-1);最小生成树（prim算法和kruskal算法）收藏 最小生成树（prim算法）用最小生成树的解决的经典问题：若要在n个城市间建设通信网路，给出任意两个城市的距离和每米通信网路的造价，问怎样设计网络可以使网路的造价最小。在n个点中间最多可以有n(n-1)/2条无向边存在，最多可以有n(n-1)个有向边存在。只要n-1边就可以将n个点连接成一个生成树。Prim算法：自己感觉很像缔结斯特拉算法。步骤：1. 随便找一个点，设置为已使用。2. 找已使用点和未使用点之间所有连线中最短的一条，然后将这条连线中未使用的点列入已使用。3. 如此反复1，2直到说有的点变成已使用点。/map中存储着全图,n(n+1)条线的情况.num表示点的个数,treemap是生成的树void prim(int mapN,int num,int treemapN)/treemap初始化为0. bool *used=new boolnum;/用来判断该点是否已经用过 int count=num;/用来计数 int point=0;/用来代表即将加入的点的上一个点 int willuse=0;/用来代表即将加入的点 int mindage;/用来代表当前的最小路程 /初始化used used0=true; for(int m=1;mnum;m+) usedm=false; while(count-) .mindage=9999999; for(int i=0;inum;i+) . for(int j=0;jnum;j+) . if(usedj)/find a used point . for(int k=0;knum;k+) . if(!usedk&mapjkmindage)/find unused point . point=j;willuse=k;mindage=mapjk; treemappointwilluse=treemapwillusepoint=1;/将point到willuse这两个点联通 usedwilluse=1;/将willuse加入已用集合. kruskal算法:步骤：1. 将每一个点看成一个连通分量，在连通分量间找最短的边，然后连到一起，那么在图中就有n-1个连通分量了。2. 在现在的连通分量的情况下找任意两个连通分量间最短的边中最短的边，将这两个连通分量连到一起，这样往复知道所有的点在同一个联通分量中就可得到最小生成树。代码如下：void kruskal(int mapN,int num,int treemapN)/treemap初始化为0. int *flag=new intnum;/用来判断连个点是不是在同一个连通分量里 int count=num-1;/用来为边计数要n-1条边 int mindis,number1,number2,from,to;/中间变量 for(int i=0;inum;i+) flagi=i+1;/将每个点的划分成一个连通分量 while(count-) . mindis=99999999;/用来记录当前最小的边 for(int j=0;jnum;j+) . for(int g=0;gnum;g+) . if(j=g) continue; /当两个点不在同一个连通分量中并且他们的边比较小时. else if(flagj!=flagg&mapjgflagg?flagj:flagg); number2=(flaggflagj?flagj:flagg); from=j; to=g; treemapfromto=treemaptofrom=1; /为1即连通 for(int m=0;mnum;m+) . if(flagm=number2) flagm=number1; 测试用语句:#include using namespace std;#define N 6/语句插入位子.int main(). int map66=. .100,6,1,5,100,100, .6,100,5,100,3,100, .1,5,100,5,6,4, .5,100,5,100,100,2, .10