Java教程

最小生成树算法Kruskal

本文主要是介绍最小生成树算法Kruskal,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 最小生成树算法
    • 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;
}
这篇关于最小生成树算法Kruskal的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!