MST最小生成树 Kruskal算法

所谓最小生成树，就是在一个具有N个顶点的带权连通图G中，如果存在某个子图G’，其包含了图G中的所有顶点和一部分边，且不形成回路，并且子图G’的各边权值之和最小，则称G’为图G的最小生成树。

由定义我们可得知最小生成树的两个性质：

•最小生成树不能有回路。

•最小生成树边的个数等于顶点的个数减一。

Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法等。两种算法都是贪婪算法的应用。

Kruskal算法的基本思想是将图G中的边按权值从小到大依次选取，若

选取的边使生成树不形成回路，则把它并入TE中，若形成回路则将其

舍弃，直到TE中包含N-1条边为止，此时TE为最小生成树

关键问题

如何判断欲加入的一条边是否与生成树中边构成回路？

将各顶点划分为所属集合的方法来解决，每个集合的表示一个无回路的子集。开始时边集为空，N个顶点分属N个集合，每个集合只有一个顶点，表示顶点之间互不连通。

当从边集中按顺序选取一条边时，若它的两个端点分属于不同的集合，则表明此边连通了两个不同的部分，因每个部分连通无回路，故连通后仍不会产生回路，此边保留，同时把相应两个集合合并。

这可以用并查集来完成。

过程图如下

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int parent[];

struct Edge
{
    int a;
    int b;
    int value;
};

Edge edge[];

int find(int index)
{
    if(index == parent[index])
        return index;
    else
        return parent[index] = find(parent[index]);
}

void join(int a,int b)
{
    int fa = find(a),fb = find(b);
    if(fa != fb)
        parent[fa] = fb;
}

bool same(int a,int b)
{
    int fa = find(a),fb = find(b);
    return fa == fb;
}

bool cmp(const Edge &x,const Edge &y)
{
    return x.value < y.value;
}

int main()
{
    int n,m,ans=,a,b,v,e=;
    cin >> n >> m ;
    for(int i=;i<=n;i++)
        parent[i] = i;
    for(int i=;i<=m;i++)
    {
        cin >> edge[i].a >> edge[i].b >> edge[i].value;
    }
    sort(edge+,edge+m+,cmp);
    for(int i=;i<=m;i++)
    {
        if(!same(edge[i].a,edge[i].b))
        {
            join(edge[i].a,edge[i].b);
            ans += edge[i].value;
            e++;
        }
        if(e == n-)
        {
            break;
        }
    }
    if(ans == )//无解，不要在意orz
    {
        cout<<"orz";
    }
    else
    {
        cout << ans;
    }

}