Kruskal算法 | 野生开发者

Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，那么这里我们就可以用到一个工具：并查集。实际上，Kruskal算法就是基于并查集的贪心算法。

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

struct node{
    int head, tail;
    int len;
};

bool cmp(const node& a, const node& b){
    return a.len < b.len;
}

void kruskal(vector<node> &arr, vector<bool> &visited){
    for(int i = 0; i < arr.size(); i++)
        cin >> arr[i].head >> arr[i].tail >> arr[i].len;
    sort(arr.begin(), arr.end(), cmp);
    for(int i = 0; i < visited.size(); i++)
        visited[i] = false;
    int ans = 0;
    for(int i = 0; i < arr.size(); i++){
        if((!visited[arr[i].head]) || (!visited[arr[i].tail])){
            visited[arr[i].head] = visited[arr[i].tail] = true;
            ans += arr[i].len;
            cout << arr[i].head << "-->" << arr[i].tail << ": " << arr[i].len << endl;
        }
    }
    cout << ans << endl;
}

int main(){
    int N, M;  //N is the number of edges, M is the number of nodes
    cin >> N >> M;
    vector<node> arr(N);
    vector<bool> visited(M);
    kruskal(arr, visited);
    return 0;
}
/*
Input:
8 6
0 1 2
0 2 1
1 3 5
2 3 4
1 2 3
2 4 1
4 5 2
3 5 3
Output:
0-->2: 1
2-->4: 1
0-->1: 2
4-->5: 2
3-->5: 3
9
*/