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;
    }

}