最小生成树算法合集

 

1  kruskal

1 struct seg 2 { 3 int a; 4 int b; 5 int p; 6 }; 7 seg v[100];//边的最大值 8 int father[30];//最大限为点的最大值 9 int cmp(seg a,seg b) 10 { 11 return a.p<b.p; 12 } 13 int Find(int x) 14 { 15 if(father[x]==x) 16 return x; 17 else return Find(father[x]); 18 } 19 int kruskal(int n)//传入边个数，输出最小边长度 20 { 21 int i,j,k; 22 int fx,fy; 23 int len=0; 24 for(i=0; i<30; i++) 25 father[i]=i; 26 for(i=0; i<n; i++) 27 { 28 fx=Find(v[i].a); 29 fy=Find(v[i].b); 30 if(fx!=fy) 31 { 32 father[fx]=fy; 33 len+=v[i].p; 34 } 35 } 36 return len; 37 } 38 int main() 39 { 40 for() 41 { 42 k=0; 43 v[k].a=a; 44 v[k].b=b; 45 v[k++].p=length; 46 } 47 sort(v,v+k,cmp); 48 printf("%d\n",kruskal(k)); 49 return 0; 50 } View Code

2 prim

1 int G[30][30];//保存图关系 2 void maxG(int n)//初始化图 3 { 4 int i,j; 5 for(i=0; i<n; i++) 6 for(j=0; j<n; j++) 7 G[i][j]=INF; 8 } 9 int prim(int n)//传入点个数，输出最小生成图长度 10 { 11 int i,j,k,t; 12 int len=0,min; 13 int D[30];//保存0到任一点长度，可修改起始点 14 int visit[30]; 15 for(i=0; i<n; i++) 16 { 17 D[i]=G[i][0]; 18 visit[i]=0; 19 } 20 visit[0]=1;//起始点变，0变s 21 D[0]=0; 22 for(i=1; i<n; i++) 23 { 24 k=0; 25 min=INF; 26 for(j=0; j<n; j++) 27 { 28 if(!visit[j]&&min>D[j]) 29 { 30 min=D[j]; 31 k=j; 32 } 33 } 34 visit[k]=1; 35 len+=min;//长度++ 36 for(t=0; t<n; t++) 37 { 38 if(!visit[t]&&min>D[j]) 39 { 40 if(!visit[t]&&G[k][t]<D[t]) 41 D[t]=G[k][t]; 42 } 43 } 44 } 45 return len; 46 } 47 int main() 48 { 49 maxG(n); 50 for(i=0; i<n-1; i++) 51 { 52 for(j=0; j<s1n; j++) 53 { 54 G[i][j]=G[j][i]=min(G[i][j],length); 55 } 56 } 57 printf("%d\n",prim(n)); 58 } 59 60 return 0; 61 } View Code

 

 

转载于:https://www.cnblogs.com/Skyxj/p/3221254.html