Kruskal算法

（一）Kruskal算法又称避圈法，是解决赋权图最小生成树问题的经典算法。

（二）算法的基本思想：在与已选取的边不构成回路的边中选取最小者。

　　　　先将所有的边按权值大小排序，然后依次加边，避免生成圈，直到所有点都包含在内，这样得到的一颗权值最小的树叫做最小生成树。

（三）算法的基本步骤：

　　　　设G=(V,E,W)，将G中非环边按权从小到大排序：e1, e2, …, em。

　　　　(1) 取e1在T中。

　　　　(2) 查e2，若e2与e1不构成回路，取e2也在T 中，否则弃e2。

　　　　(3) 再查e3,…, 直到得到生成树(m=n-1)为止。

（四）三点说明

　　　　1.使用并查集实现Kruskal算法.

　　　　2.算法的关键是避圈。

　　　　3.最小生成树的边数等于点数减一.

（五）算法涉及到的几个函数

　　1.寻找根节点的函数

1 int find(int r)
2 {
3     return r==father[r]?r:find(father[r]);
4 }

　　2.定义排序函数

1 int cmp(node x,node y)
2 {
3     return x.c<y.c;
4 }

　　3.合并各连通分量

 1 for(i=0;i<m;i++)//一共有m条边，所有循环到m
 2 {
 3    int fa=find(s[i].a);
 4    int fb=find(s[i].b);
 5    if(fa!=fb)
 6    {
 7       father[fa]=fb;
 8       sum+=s[i].c;
9    }
10　}

（六）下面给出一道已经AC的题

HDU2122

题目

ice_cream’s world becomes stronger and stronger; every road is built as undirected. The queen enjoys traveling around her world; the queen’s requirement is like II problem, beautifies the roads, by which there are some ways from every city to the capital. The project’s cost should be as less as better.

InputEvery case have two integers N and M (N<=1000, M<=10000) meaning N cities and M roads, the cities numbered 0…N-1, following N lines, each line contain three integers S, T and C, meaning S connected with T have a road will cost C.OutputIf Wiskey can’t satisfy the queen’s requirement, you must be output “impossible”, otherwise, print the minimum cost in this project. After every case print one blank.Sample Input

Sample Output

10

impossible

代码

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 struct node{
 5     int a,b,c;
 6 }s[10010];
 7 int father[10010];
 8 int find(int r)
 9 {
10     return r==father[r]?r:find(father[r]);
11 }
12 int cmp(node x,node y)
13 {
14     return x.c<y.c;
15 }
16 int main()
17 {
18     int n,m,i;
19     while(~scanf("%d%d",&n,&m))
20     {
21         for(i=0;i<n;i++)//初始化
22         {
23             father[i]=i;
24         }
25         for(i=0;i<m;i++)
26         {
27             scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
28         }
29         sort(s,s+m,cmp);//求的是最小的生成树，所以按照权值 增序排列
30         int count=0,sum=0;
31         for(i=0;i<m;i++)//一共有m条边，所有循环到m
32         {
33             int fa=find(s[i].a);
34             int fb=find(s[i].b);
35             if(fa!=fb)
36             {
37                 father[fa]=fb;
38                 sum+=s[i].c;
39                 count++;//除了这一点都是克鲁斯卡尔算法模板
40             }
41         }
42         if(count!=n-1)//是否是n-1条边 即建立了一个满足条件的最小生成树
43         {
44             printf("impossible

");
45         }
46         else
47         printf("%d

",sum);
48     }
49     return 0;
50 }