Kruskal 最小生成树代码实现

1. 代码实现

Kruskal 最小生成树算法，算法的大概思路为：将所有边升序排列，然后从值最小的边开始取边，如果当前的边添加到已取的边中不构成环，则取该边，否则舍弃这条边，去判断下一条边，重复上述操作一直到取到 n-1 条边，这n-1条边就是最小生成树的路径，代码实现如下所示：

// Kruskal代码实现
// 时间复杂度 elog(e), e为边数

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

// s为起点，e为终点，v是这条边的值
typedef struct edge {
	int s, e;
	ll v;
}Edge;

bool cmp(Edge A, Edge B) {
    return A.v<B.v;
}

const int N = 201000;
Edge a[N];
// f[i]!=-1 则代表 i 与 f[i] 之间有一个节点
int f[N];

int Find(int x) {
    if(f[x] == -1) return x;
    return f[x] = Find(f[x]);
}

// n为节点数、m为边数
int n, m;

ll Kruskal() {

    // 初始化 f[]
    for(int i=0; i<N-10; i++) {
        f[i] = -1;
    }

    int sRoot, eRoot;
    int num = 0;
    ll ans = 0;
    for(int i=0; i<m; i++) {
        sRoot = Find(a[i].s);
        eRoot = Find(a[i].e);

        // 未构成环
        if(sRoot != eRoot) {
            num ++;
            ans += a[i].v;
            f[sRoot] = eRoot;
        }

        if(num >= n-1) {
            break;
        }
    }
    if(num >= n-1) return ans;
    return -1;
}

int main() {
    cin >> n >> m;

    int s, e, v;
    for(int i=0; i<m; i++) {
        cin >> s >> e >> v;
        a[i].s = s;
        a[i].e = e;
        a[i].v = v;
    }

    // 将边升序排列
    sort(a, a+m, cmp);
    cout << Kruskal();

    return 0;
}

2. OJ题测试

100 分代码如下所示：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

// s为起点，e为终点，v是这条边的值
typedef struct edge {
	int s, e;
	ll v;
}Edge;

bool cmp(Edge A, Edge B) {
    return A.v<B.v;
}

const int N = 201000;
Edge a[N];
// f[i]!=-1 则代表 i 与 f[i] 之间有一个节点
int f[N];

int Find(int x) {
    if(f[x] == -1) return x;
    return f[x] = Find(f[x]);
}

// n为节点数、m为边数
int n, m;

ll Kruskal() {

    // 初始化 f[]
    for(int i=0; i<N-10; i++) {
        f[i] = -1;
    }

    int sRoot, eRoot;
    int num = 0;
    ll ans = 0;
    for(int i=0; i<2*m; i++) {
        sRoot = Find(a[i].s);
        eRoot = Find(a[i].e);

        // 未构成环
        if(sRoot != eRoot) {
            num ++;
            ans = a[i].v;
            f[sRoot] = eRoot;
        }

        if(num >= n-1) {
            break;
        }
    }
    if(num >= n-1) return ans;
    return -1;
}

int main() {
    int root;
    cin >> n >> m;
    cin >> root;

    int s, e, v;
    for(int i=0; i<m; i++) {
        cin >> s >> e >> v;
        a[i*2].s = s;
        a[i*2].e = e;
        a[i*2].v = v;

        a[i*2+1].e = s;
        a[i*2+1].s = e;
        a[i*2+1].v = v;
    }

    // 将边升序排列
    sort(a, a+2*m, cmp);
    cout << Kruskal() << endl;

    return 0;
}

/**
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

**/