• 最小生成树算法
  • 1、Kruskal
    • 1.1 算法简介
    • 1.2 C++实现

最小生成树算法

最小树定义：

• 给定网络\(G=(N,E,W)\)，设\(T=(N,E')\)为\(G\)的一个支撑树，令\(W(T)=\sum_{e\in E'}W(e)\)为\(T\)的权（或长）。\(G\)中权最小的支撑树称为\(G\)的最小树。

1、Kruskal

• 并查集:用一个元素代表一组元素，用于查询不同元素是否属于同一组，以及合并组

  int par[MAXN];//每个元素所在集合代表元素的编号
  int rnk[MAXN];//所在集合的大小；
  //初始化
  for(int i=0; i<n; i++){
      par[i]=i;  
      rnk[i]=1;
  }  
  int find(int x){
    //查找x所在集合的代表元
    if(par[x]==x)//到达根
      return x;
    //直接路径压缩，忽略节点之间关系，把节点挂到根上
    else par[x] = find(par[x]);
  }
  bool unite(int x,int y){
    //把一个分组挂到另一个分组，返回合并是否成功
    x=find(x);
    y=find(y);
    if(x == y) return false;
    if(rnk[x]>rnk[y]){//把小树挂在大树上,防止出现高树
        par[y]=x;
        rnk[x] = (rnk[y] += rnk[x]);
        //可以直接rnk[x]+=rnk[y]
    }
    else{
        par[x]=y;
        rnk[y] = (rnk[x] += rnk[y]);
        //可以直接rnk[y]+=rnk[x]
    }
    return true;
  }
  

1.1 算法简介

Kruskal是1956年首次提出的求最小生成树的算法，后来Edmonds把该算法称为贪心算法，其基本思路就是从G中的m条边中选取n-1条权尽可能小的边，使其不构成回路，从而构成一个最小树。

• 第一步：把图按照边权的大小从小到大排列起来，初始化一个已选中的边集，或计数器
• 第二步：不断从加入之后不构成环的边中选择权最小的边加入边集
• 第三步：如果边集中边的数量达到n-1，则停止，否则继续选边加边

1.2 C++实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
struct edge{
    int u,v,w;
    //重载比较符，为了按照边权排序
    bool operator < (const edge& t){
        return w < t.w;
    }  
}e[MAXN];
int m,n;
int par[MAXN];//每个元素所在集合代表元素的编号
int rnk[MAXN];//所在集合的大小；

void init(int n){
    for(int i=0; i<n; i++)
        par[i]=i; 
}

int find(int x){
    if(par[x]==x) return x;
    else par[x] = find(par[x]);
}

bool unite(int x,int y){
    x=find(x);y=find(y);
    if(x == y) return false;
    par[x]=y;
    return true;
}

int kruskal(){
    std::sort(e+1,e+1+m);
    int cnt=0,minum_tree_size=0;
    for(int i=1; i<=m; i++){
        if(unite(e[i].u,e[i].v)){
            minum_tree_size += e[i].w;
            if(++cnt == n-1)break; 
        }
    }
    return cnt==n-1? ans : -1;
}

int main(){
    scanf("%d%d", &m,&n);
    init(n);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    printf("%d\n",kruskal())
    return 0;
}