复习图的一些算法，使用c++实现

最小生成树（Kruscal）

思路：每次加入最短的边，要求加入后不成环（即两个顶点不连通）。

整个算法分成两部分：一是并查集，判断点的连通性，二是排序之后的选择以及结点连通性的修改。

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

vector<int> fatherList;

struct link{
    int start,end,weight;
    link(){};
    link(int s,int e,int w){
        start = s;
        end = e;
        weight = w;
    }
};

bool compare(link l1, link l2){
    return l1.weight<l2.weight;
}

int father(int x){
    if(fatherList[x]==x)
        return x;
    return father(fatherList[x]);
}

void combine(int x, int y){
    fatherList[father(x)] = father(y);
}

int main(){
    int num;
    while(cin>>num){
        if(num==0)
            break;
        fatherList.clear();
        for(int i=0;i<=num;i++)
            fatherList.push_back(i);
        int n = num*(num-1)/2;
        vector<link> list;
        while(n-->0){
            int s,e,w;
            cin>>s>>e>>w;
            link tmp(s,e,w);
            list.push_back(tmp);
        }
        sort(list.begin(),list.end(),compare);
        int cnt = 0, sum=0, idx=0;
        while(cnt++<num-1){
            while(father(list[idx].start)==father(list[idx].end))
                idx++;
            sum+=list[idx].weight;
            combine(list[idx].start,list[idx].end);
            idx++;
        }
        cout<<sum<<endl;
    }
    return 0;
}

//输入样例
// 3
// 1 2 1
// 1 3 2
// 2 3 4
// 4
// 1 2 1
// 1 3 4
// 1 4 1
// 2 3 3
// 2 4 2
// 3 4 5
// 0