Kruskal算法 --- 图的最小生成树（并查集）

Kruskal算法：使用n-1条边连接n个顶点，根据顶点之间权值的不同从而生成了最小生成树

题目描述

要求将这些顶点都能够连接，并且权值总和最小

Input
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2

Kruskal算法思路：按照权值对路径进行排序，然后从最小的开始选，依次选择每一条边，直到选择了n-1条边让整个图连通为止（判断两个顶点是否连通，可以通过广搜、深搜来完成，但是比较慢），可以通过并查集的实现，来判断两个顶点是否连通

代码如下

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge
{
    int u,v,w;
};
edge e[10];//用来存储边的关系
int n,m;
int parent[7],sum,con;//并查集所需的变量
//寻找顶点的祖父
int getf(int v)
{
    if(parent[v] == v)
        return v;
    else
    {
        parent[v] = getf(parent[v]);//路径压缩
        return parent[v];
    }
}
//判断两个顶点是否在一个集合
bool Merge(int v, int u)
{
    int t1,t2;
    t1 = getf(v);
    t2 = getf(u);
    if(t1 != t2)
    {
        parent[t2] = t1;
        return 1;
    }
    return 0;
}

bool cmp(edge a,edge b)
{
    return a.w < b.w;
}

int main()
{
    int i;
    scanf("%d %d",&n,&m);
    for(i = 0;i < m;i++)
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    //按权值从小到大进行排序
    sort(e, e+m, cmp);
    //并查集初始化
    for(i = 1;i <= n;i++)
        parent[i] = i;
    //Kruskal算法核心
    for(i = 0;i < m;i++)
    {
        //判断一条边的两个顶点是否已连通，即判断是否在一个集合中
        //不在一个集合
        if(Merge(e[i].u, e[i].v))
        {
            con++;
            sum += e[i].w;
        }
        if(con == n-1)
            break;
    }
    printf("%d\n",sum);
    return 0;
}