HiHo一下 最小生成树 Week26 Week27

HiHo

描述

这两周练习的是最小生成树的算法，一个是基于点的Prim算法，另一个是基于边的Kruscal算法。

思路

对于Prim算法，我们将点集划分为两个子集，其中那个一个初始为空，称为已处理集，另一个初始化为全集，称为未处理集。我们将任意一个点加入到已处理集，并找出连接两个集合中点的最短边，换言之，我们要找的边的一头在已处理集，一头在未处理集，这种边可能有很多条，我们感兴趣的是权值最小的那条。找到这条边后将其加入生成树，并把边连接的未处理集中的点移出到已处理集。不断反复以上操作直到完成n-1条边的寻找也就是完成生成树的构造。
对于Kruscal算法。我们会用到并查集，一开始将所有边按权值排序，n个点分别在n个集合。取出权值最小的边，如果边两头的点不在同一集合，那就将该边加入生成树，并将两个集合合并，如果在同一集合那就继续取边。如此操作直到完成树的构造。
Prim算法复杂度为$O(E+VlogV)$
Kruscal复杂度为$O(ElogE)$

代码

• Prim

#include<iostream>
#include<queue>
using namespace std;
#define MAX 1005
struct edge{
    int x;
    int y;
    int length;
    bool operator < (const edge &a) const{
        return a.length < length;
    }
};
int map[MAX][MAX];
std::vector<int> flag(MAX+1,false);
std::priority_queue <edge> tree;
int main(){
    int n;
    int sum = 0;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cin >> map[i][j];
    }
    flag[1] = true;
    int t = 1;
    for(int i=1;i<n;i++){
        for(int j=1;j<=n;j++){
            if(t!=j&&!flag[j]){
                edge temp;
                temp.length=map[t][j];
                temp.x = t;
                temp.y = j;
                tree.push(temp);
            }
        }
            while((flag[tree.top().x] xor flag[tree.top().y])==0) tree.pop();
        if(flag[tree.top().x]) t = tree.top().y;
            else t = tree.top().x;
            sum += tree.top().length;
            flag[t] = true;
            tree.pop();
    }
    cout << sum;
    return 0;
}

• Kruscal

#include<iostream>
#include<queue>
using namespace std;
#define MAX 100005
int flag[MAX];
struct edge{
    int x;
    int y;
    int length;
    bool operator < (const edge &a) const{
        return a.length < length;
    }
};
int seekFa(int i){
    if (flag[i]!=i) flag[i] = seekFa(flag[i]);
    return flag[i];
}
void unionFa(int x,int y){
    int aa = seekFa(x);
    int bb = seekFa(y);
    if(aa>bb) flag[aa] = bb;
    else flag[bb] = aa;
}
std::priority_queue <edge> tree;
int main(){
    int n,m;
    int sum = 0;
    cin >> n >>m;
    for(int i=1;i<=n;i++){
        flag[i] = i;
    }
    while(m--){
        int a, b ,c;
        cin >>a >> b >> c;
        edge temp;
        temp.x = a;
        temp.y = b;
        temp.length = c;
        tree.push(temp);
    }
    for(int i=1;i<n;i++){
        while((seekFa(tree.top().x))==(seekFa(tree.top().y))) 
            tree.pop();
        sum +=tree.top().length;
        unionFa(flag[tree.top().x],flag[tree.top().y]);
        tree.pop();
    }           
    cout << sum;
    return 0;
}