最小生成树

算法目标

最小生成树是找出一个图中总边权最小的那棵树的算法。

在其中分为Prim和Kruskal两种算法。

经典例题:浇地

Prim

先选任意节点为树的根节点,然后找到所有在已选择的节点中找到最短的一条和未选择的节点相连的边,然后将未选择节点变为选择的节点,即每次找可到达的最短边并加入节点。

模板

模板题

#include<bits/stdc++.h>
using namespace std;
bool vis[10005];
int n,m;
struct node{
    int v,w;
};
//以边权为参考量重载运算符
struct cmp{
    bool operator () (node a,node b){
        return a.w>b.w;
    }
};
vector<node> G[10005]; 
int prim(){
    int cnt=0;
    priority_queue<node,vector<node>,cmp> q;
    node cur,nxt;
    cur.v=1;
    cur.w=0;
    q.push(cur);//初始化 
        //找出最短边
    while(!q.empty()){
        cur=q.top();
        //cout << "cur = " << cur.v << endl;
        q.pop();
        if(vis[cur.v]==1){
            continue;
        }
        cnt += cur.w;//
        vis[cur.v]=1;
        int Size=G[cur.v].size();
        for(int i=0;i<Size;i++){//添加这条边可以达到的所有点
            if(!vis[G[cur.v][i].v]){
                nxt.v=G[cur.v][i].v;
                nxt.w=G[cur.v][i].w;
                q.push(nxt);
            }
        }
    }
    return cnt;
}
//判断是不是可行,即有无无法联通的节点
bool check(){
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            return false;
        }
    }
    return true;
}
int main(){
    cin>>n>>m;
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        node tmp;
        tmp.v=b;
        tmp.w=c;
        G[a].push_back(tmp);//双向边
        tmp.v = a;
        G[b].push_back(tmp);
    }
    int k=prim();
    bool can=check();
    if(can==false){
        cout<<"orz";
        return 0;
    }
    cout<<k;
    return 0;
}

Kruskal

kruskal算法与prim算法类似,都是找出最短边。但是prim是找出与已选择节点连接的边,而Kruskal是找出所有未用过的边中的最短边,并且选择某个点之后需要判断是否存在环。

先排序边,然后一个一个取出,如果在相同集合内就不管,如果不在同一集合内就取出这条边。

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct kkk{
    int u;
    int v;
    int w;
}edge[200005];
int cmp(kkk a,kkk b){
    return a.w<b.w;
}
int head[5005];
int find(int a){
    if(head[a]==a){
        return a;
    }
    return head[a]=find(head[a]);
}
void unite(int a,int b){
    int fa=find(a);
    int fb=find(b);
    head[fa]=fb;
    return ;
}
int ans=0;
void kruskal(){
    int a, b, c;
    for(int i=0;i<m;i++){
        a = edge[i].u;
        b = edge[i].v;
        c = edge[i].w;
        if(find(a)!=find(b)){
            unite(a,b);
            ans+=c;
        }
    }
    return ;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        head[i]=i;
    }
    for(int i=0;i<m;i++){
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    }
    sort(edge,edge+m,cmp);//排序边
    kruskal();
    for(int i=1;i<=n;i++){
        if(find(i)!=find(1)){
            cout<<"orz";
            return 0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/502/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者