kruskal基礎算法

/*Kruskal算法
1:将所有邊按照從小到大的順序排列
2:依次将權值最小的邊加入生成樹的子集當中
3:重複以上的步驟直到找出n-1條邊為止
注：Kruskal适合求稀疏圖問題，而prim算法适合求稠密圖問題
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
const int maxn =  + ;
int n, m, parent[maxn], childNum[maxn], sum;

struct Edge {
    int u, v, val;
} edge[maxn];

vector<Edge> ans;

bool cmp(const Edge & s1, const Edge & s2) {
    return s1.val < s2.val;
}

int UFind(int u) {
    return parent[u] == u ? u : UFind(parent[u]);
}

bool join(int u, int v) {
    int root1 = UFind(u);
    int root2 = UFind(v);

    if(root1 == root2)  return false;   //存在環

    if(childNum[root1] > childNum[root2]) {     //将節點數少的點連接配接到節點數量多的樹上面
        parent[root2] = root1;
        childNum[root1] += childNum[root2];
    }
    else {
        parent[root1] = root2;
        childNum[root2] += childNum[root1];
    }
}

bool kruskal() {
    sort(edge, edge + m, cmp);
    int sideNum = ;    //邊的個數
    for(int i = ; i < m; i++) {
        if(join(edge[i].u, edge[i].v)) {
            sideNum++;
            sum += edge[i].val;
            ans.push_back(edge[i]);
        }

        if(sideNum == n - )    return true;    //如果邊的個數到達n-1條，則最小生成樹的建構完成
    }
    return false;
}

int main()
{
    cout << "enter the number of vertexes and sides:" << endl;
    cin >> n >> m;

    for(int i = ; i < n; i++) {    //初始化
        parent[i] = i;
        childNum[i] = ;
    }
    sum = ;

    for(int i = ; i < m; i++)
        cin >> edge[i].u >> edge[i].v >> edge[i].val;

    ans.clear();

    if(kruskal()) {
        cout << "kruskal path:" << endl;
        for(int i = ; i < ans.size(); i++)     cout << ans[i].u << "->" << ans[i].v << endl;
        cout << "the sum is:" << endl;
        cout << sum << endl;
    }
    else
        cout << "error" << endl;
    return ;
}