kruscal 算法 最小生成树模板（hdu 1233 ）

kruskal 和 prim 算法都是求最小生成树经常用到的算法，其中，prim 适用于稠密图（边较多），而 kruskal 更适用于稀疏图（边较少）。其时间复杂度为 O（elog2(e)）. 其中，e 为图的边 AD 和 CE 是最短边，长度为 5，AD 是 第一个选择的边，被突出显示。 CE 现在是不构成循环的第二条最短的边，长度为 5，突出显示为第二个边。 下一条边，长度为 6 的 DF，突出显示为第三条边。 接下来的最短边是 AB 和 BE，都是长度为 7. 随机选一条，这里我们选 AB，并且突出显示。边缘 BD 以红色突出显示，因为在 B 和 D 之间已经存在一条路径（绿色），所以如果选择它，它将形成一个循环（ABD）。 继续突出显示下一条最小的边，BE 长度为 7. 许多个边缘以红色显示：BC，因为它会形成回路 BCE。DE，因为它会形成回路 DEBA 和 FE 因为它会形成 FEBAD。 最后，该过程以长度为 9 的边 EG 结束，并找到最小生成树。 kruskal 和 prim 都是基于贪心的思想，其中，kruskal 是每次将属于不同集合的最小的一条边合并。这样，一直合并下去，最终会得到一棵最小生成树（总点数一定，连接的点不断增多，所以未连接的点就会逐渐减少直到为 0），需要注意的是，kruskal 是基于并查集优化的，所以了解 kruskal 算法之前，应该先看一下并查集。

1. 使用结构体储存边的信息：

   struct edge{

   int a,b;        //a为起点，b为终点
   int v;          //v为该边的权值
   

   }s[maxn];///将结构体按权值排序后，依次进行合并操作

1. 并查集合并及路径压缩：

int pre[maxn];    ///各集合

int Find(int a){        ///寻找祖宗节点的同时进行路径压缩
    int root = a;
    int tmp;
    while(root != pre[root])root = pre[root];
    while(a != root){
        tmp = a;
        a = pre[a];
        pre[tmp] = root;
    }
    return root;
}

void combine(int a,int b){    ///合并a，b两个集合，这里我们规定将较大的数并入到较小的数中
    int x = Find(a);
    int y = Find(b);
    if(x > y)
        swap(x,y);
    pre[y] = x;
}
3;kruskal 主代码：

int kruscal(int n,int m){
    int ans = 0;
    For(i,m){
        if(Find(s[i].a)!=Find(s[i].b)){    ///如果a点所在的集合和b点所在的集合不相交
            combine(s[i].a,s[i].b);        ///合并两个集合
            ans += s[i].v;                
            n--;
        }
        if(n == 1)    ///当已经连了n-1条边时，就已经构成了最小生成树因为每n个点要连在一起只需要n-1条线即可
            break;
    }
    return ans;
}
```   

* * *

例题：hdu1233 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府 “畅通工程” 的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。  

**Input** 

测试输入包含若干测试用例。每个测试用例的第 1 行给出村庄数目 N (< 100)；随后的 N (N-1)/2 行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从 1 到 N 编号。  当 N 为 0 时，输入结束，该用例不被处理。  

**Output** 

对每个测试用例，在 1 行里输出最小的公路总长度。  

**Sample Input** 

3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 

**Sample Output** 

3 5 

Huge input, scanf is recommended.     

裸 kruskal 即可 参考代码：
```cpp
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#define For(i,n) for(int i=0;i<n;i++)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e4+5;
typedef long long ll;

struct edge{
    int a,b;
    int v;
}s[maxn];

int pre[maxn];

bool cmp(edge a,edge b){return a.v < b.v;}
int Find(int a){
    int root = a;
    int tmp;
    while(root != pre[root])root = pre[root];
    while(a != root){
        tmp = a;
        a = pre[a];
        pre[tmp] = root;
    }
    return root;
}

void combine(int a,int b){
    int x = Find(a);
    int y = Find(b);
    if(x > y)
        swap(x,y);
    pre[y] = x;
}

int kruscal(int n,int m){
    int ans = 0;
    For(i,m){
        if(Find(s[i].a)!=Find(s[i].b)){
            combine(s[i].a,s[i].b);
            ans += s[i].v;
            n--;
        }
        if(n == 1)
            break;
    }
    cout << ans <<endl;


}
int main() {
    int n;
    int a,b,c;
    int cnt;
    while(cin >> n && n){
        mem(s);
        For(i,n+1)
            pre[i] = i;
        cnt = 0;
        For(j,n*(n-1)/2){
            cin >> a >> b>>c ;
            s[cnt].a = a;
            s[cnt].b = b;
            s[cnt++].v = c;
        }
        sort(s,s+cnt,cmp);            ///将边的权值按从小到大排序
        kruscal(n,n*(n-1)/2);         ///一共n个点，n*(n-1)/2条边
    }


    return 0;
    }

复制