最小生成树算法合集

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
",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
",prim(n));
58 }
59 
60 return 0;
61 }

View Code