学最小生成树有感

Superiority · 2024-12-03 06:41:20 · 算法·理论

最小生成树

最小生成树即一个连通图（要有权值）中一棵边权和最小且包含所有顶点的树（我们知道连接 n 个顶点最少要 n-1，又由于我们要树的权值最小，所以我们贪心的只选择 n-1 条边 ），那么这棵树就被称为最小生成树。

Kruskal算法

首先我们可以把一个图看为没有任何边的森林。我们最后要让它们构成一棵树（即没有回路，且连通），我们很容易的想到并查集。那现在后面就很好得到了，我们可以尽量贪心的选择权值(边权)最小的一个节点合并，不过注意判断是否在一个集合，不然就不是一棵树了。

• 正确性证明：如果这棵树不是最小生成树则一定会有至少一条边不一样，且这条边小于原本选择的边，而由于是贪心思想，则这个边一定会在前面被加入树中。

Code

#include<bits/stdc++.h>//problem:P3366 (algorithm: Kruskal)
using namespace std;
#define zjj long long
const int MAXN=1e6+5;
const int INF=1e9;
int T=1;
int n,m,st,en;
int idx,cnt,ans;
bool flag;
int f[MAXN];
struct S{
    int pre,nxt;
    int dis;        
}s[MAXN];
bool cmp(S a,S b){
    return a.dis<b.dis;
}
void init(){
    for(int i=1;i<=n;i++) f[i]=i;
}
int find(int x){//路径压缩，查找根节点
    if(x==f[x]) return x;
    f[x]=find(f[x]);
    return f[x];
}
void Union(int x,int y){//合并
    if(find(x)==find(y)) return ;
    f[find(y)]=find(x);
}
void kruskal(){//主题贪心部分
    for(int i=1;i<=m;i++){
        if(find(s[i].pre)!=find(s[i].nxt)){
            Union(s[i].pre,s[i].nxt);
            ans+=s[i].dis;
            cnt++;
        }
    }
}
void slove(){
    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++){
        cin>>s[i].pre>>s[i].nxt>>s[i].dis;
    }
    sort(s+1,s+m+1,cmp);//由于贪心选最小的，所以sort一下
    kruskal();
    if(cnt==n-1) cout<<ans<<endl;//合并n-1次后所有点都在一棵树上了，所以比联通。
    else cout<<"orz"<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // cin>>T;
    while(T--){
        slove();    
    }
    return 0;//exit(0);
}
//thinking: link->学最小生成树有感

Prim算法

Prim一种基于dijkstra的最小生成树算法