本文目录
什么是Prim算法
Prim算法Prim算法用于求无向图的最小生成树 设图G =（V，E），其生成树的顶点集合为U。 ①、把v0放入U。 ②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。 ③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。 其算法的时间复杂度为O(n^2)Prim算法实现：（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。参考程序/* Prim.cCopyright (c) 2002, 2006 by ctu_85 All Rights Reserved.*//* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */#include "stdio.h"#define maxver 10#define maxright 100int main(){int G;int i,j,k,min=maxright;int v1,v2,num,temp,status=0,start=0;restart:printf("Please enter the number of vertex(s) in the graph:\n");scanf("%d",#);if(num》maxver||num《0){printf("Error!Please reinput!\n");goto restart;}for(j=0;j《num;j++)for(k=0;k《num;k++){if(j==k)G=maxright;elseif(j《k){re:printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);scanf("%d",&temp);if(temp》=maxright||temp《-1){printf("Invalid input!\n");goto re;}if(temp==-1)temp=maxright;G=temp;}}for(j=0;j《num;j++){status=0;for(k=0;k《num;k++)if(G《maxright){status=1;break;}if(status==0)break;}do{printf("Please enter the vertex where Prim algorithm starts:");scanf("%d",&start);}while(start《0||start》num);in=1;for(i=0;i《num-1&&statusi++){for(j=0;j《num;j++)for(k=0;k《num;k++)if(G)){v1=j;v2=k;min=G;}if(!in){path=v1;path=v2;in=1;in=1;min=maxright;}}if(!status)printf("We cannot deal with it because the graph is not connected!\n");else{for(i=0;i《num-1;i++)printf("Path %d:vertex %d to vertex %d\n",i+1,path+1);}return 1;} Prim算法。设图G =（V，E），其生成树的顶点集合为U。 ①、把v0放入U。 ②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。 ③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。 其算法的时间复杂度为O(n^2)参考程序//Prim 算法 读入顶点数(n)、边数(m)，边的起始点和权值 用邻接矩阵储存//例如//7 12 (7个顶点12条边)//1 2 2//1 4 1//1 3 4//2 4 3//2 5 10//3 4 2//4 5 7//3 6 5//4 6 8//4 7 4//5 7 6//6 7 1#include 《stdio.h》#include 《string.h》int main(){int m , n;int a;int s , t , w;int i , j , k , min , tot;freopen("Prim.txt" , "r" , stdin);//读入数据memset(a , 0 , sizeof(a));scanf("%d %d" , &n , &m);for (i = 0; i 《 m; i ++){scanf("%d %d %d" , &s , &t , &w);a = w;}//赋初值memset(mark , 0 , sizeof(mark));memset(pre , 0 , sizeof(pre));memset(dist , 9999 , sizeof(dist));dist = 0;//Primfor (i = 1; i 《= n; i ++){min = 9999; k = 0;for (j = 1; j 《= n; j ++) if ((mark; k = j;}if (k == 0) break;mark = 1;for (j = 1; j 《= n; j ++)if ((mark 》 0)){dist;pre = k;}}tot = 0;for (i = 1; i 《= n; i ++) tot += dist;printf("%d\n" , tot);return 0;}
欧几里德 平面最小生成树算法
欧几里德算算法gcd(a,b)=ax+by：int ext_gcd(int a,int b,int& x,int& y){ int t,ret; if (!b){ x=1,y=0; return a; } ret=ext_gcd(b,a%b,x,y); t=x,x=y,y=t-a/b*y; return ret;}最小生成树（Prim算法）：//无向图最小生成树,prim算法,邻接阵形式,复杂度O(n^2)//返回最小生成树的长度,传入图的大小n和邻接阵mat,不相邻点边权inf//可更改边权的类型,pre返回树的构造,用父结点表示,根节点(第一个)pre值为-1//必须保证图的连通的!#define MAXN 200#define inf 1000000000typedef double elem_t;elem_t prim(int n,elem_t mat,int* pre){ elem_t min,ret=0; int v,i,j,k; for (i=0;i《n;i++) min=-1; for (min=0;j《n;j++){ for (k=-1,i=0;i《n;i++) if (!v)) k=i; for (v,i=0;i《n;i++) if (!v) min; } return ret;}
利用普里姆算法求解最小生成树，写出步骤或画图表示过程
《1,6》边长度未知，这里看成无穷大。历次循环中，选择两端点分别在U，V中的边中长度最小者，具体如下：1. 将1加入U中，其余点加入V中。 2. 选择边《1,7》，将7加入U中，从V中除去该点。3. 选择边《7,6》，将6加入U中，从V中除去该点。4. 选择边《1,2》，将2加入U中，从V中除去该点。5. 选择边《2,3》，将3加入U中，从V中除去该点。6. 选择边《2,4》，将4加入U中，从V中除去该点。7. 选择边《2,5》，将5加入U中，从V中除去该点。结束。由上述六条边组成的树为求得的最小生成树。
已知图G如下所示，根据Prim算法，构造最小生成树（要求给出生成过程）
①将带权连通图G=的各边按权从小到大依次排列，如e1,e2,…,em,其中e1的权最小，em的权最大，m为边数。 ②取权最小的两条边构成边集T0，即T0={e1,e2},从e3起，按次序逐个将各边加进集合T0中去，若出现回路则将这条边排除（不加进去），按此法一直进行到em，最后得到n-1条边的集合T0={e1,e2,…,en-1}，则T0导出的子图就是图G的最小生成树。
