克鲁斯卡尔（Kruskal）算法原理及图解案例

克鲁斯卡尔（Kruskal）算法原理及图解案例

引用

CSDN

1.

https://blog.csdn.net/2203_75994275/article/details/145669227

克鲁斯卡尔（Kruskal）算法是一种用于寻找图的最小生成树的算法。它通过贪心策略，逐步选择权值最小的边来构建最小生成树。本文将详细介绍克鲁斯卡尔算法的原理、实现过程，并通过图解案例和代码示例帮助读者更好地理解。

什么是克鲁斯卡尔算法？

克鲁斯卡尔算法是一种最小生成树算法，由Joseph Kruskal在1956年发表。最小生成树（Minimum Spanning Tree，MST）简单来说就是：在一个连通图中，找出其中的一个可以使各个点之间连通且路权之和最小的连接方法，然后根据这个连接方法生成一个树。

算法原理

克鲁斯卡尔算法的实现过程如下：

1. 将每一个点都看作一个无根树（独立的集合），并把这个图上的边全部存储下来，然后把所有边删掉
2. 将每一条边按权值大小从小到大排序
3. 遍历每一条存储下来的边，用并查集判断这条边所连接的两个点是否在同一个集合内（查询是否连通）：

• 若在，那么就不用添加这条边到最小生成树里去
• 若不在，这条边一定是最小生成树的一部分

这个过程利用了贪心策略：

• 如果两个点已经连通，那么先前的连接方案的权值一定是小于或等于使用这条边连接的
• 如果两个点不连通，那么使用当前边连接这两个点一定是权值最小的，因为边是按照权值从大到小排序的，往后遍历的权值一定大于等于当前边

实现过程

假设我们有一个图如下：

按照克鲁斯卡尔算法的步骤：

1. 将图中的边按权值从小到大排序
2. 依次检查每条边：

• 第一条边（2,5）：不连通，连接
• 第二条边（3,5）：不连通，连接
• 第三条边（1,3）：不连通，连接
• 第四条边（1,5）：已连通，跳过
• 第五条边（3,4）：不连通，连接
• 第六条边（2,6）：不连通，连接
• 第七条边（1,6）：已连通，跳过

最终得到的最小生成树如下：

代码实现

以下是输出最小生成树权值和的C++代码实现：

#include<bits/stdc++.h>
#define ll long long 
#define maxn 101
#define maxm 1000001
using namespace std;
ll n,m,ans;
ll fa[maxn],h[maxn]; //并查集需要用到的两个数组，分别是祖先和家族高度
struct node //使用结构体方便排序与存储
{
    ll u,v,w;
}e[maxm];
ll find(ll r) //找祖宗并更新
{
    if(r==fa[r]) return r;
    else return fa[r]=find(fa[r]);
}
void merge(ll x,ll y)  //合并集合
{
    ll fx=find(x);
    ll fy=find(y);
    if(h[fx]>h[fy]) fa[fy]=fa[fx];
    else if(h[fx]<h[fy]) fa[fx]=fa[fy];
    else
    {
        fa[fy]=fa[fx];
        h[fx]++;
    }
}
void kruskal() 
{
    int cnt=0;//选取边的数量，因为最小生成树的边数一定是n-1（要保证连通），所以可以做一个小剪枝
    for(int i=1;i<=n;i++) fa[i]=i; //初始的时候都是独立的集合
    for(ll i=1;i<=m&&cnt<=n-1;i++)
    {
        ll u=e[i].u,v=e[i].v;
        ll fu=find(u);
        ll fv=find(v);
        if(fu==fv) continue ; //若在一个集合，跳过
        cnt++; //加入最小生成树
        ans+=e[i].w;
        merge(u,v); //连接两个点
    }
}
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int main()
{
    cin>>n>>m;
    for(ll i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+1+m,cmp);
    kruskal();
    cout<<ans;
}	

通过以上步骤和代码，我们可以清晰地理解克鲁斯卡尔算法的工作原理和实现方法。