Kruskal算法常用于求连通图中的最小生成树问题，与Prim算法将一个个顶点收录进一棵“树”中的作法不同，Kruskal算法将连通图视作一篇“森林”，通过算法将“森林”合并为一棵“树”。kruskal算法相较于prime算法更暴力，核心思想是利用快排不断取最小权值的边并通过并查集维护防止产生回路

Prim算法适用于稠密图，时间复杂度为O(n^2)

Kruskal比较适用于稀疏图时间复杂度：O（eloge），是一种贪心算法:为使生成树上边的权值和最小，则应使生成树中每一条边的权值尽可能地小。

具体做法：找出森林中连接任意两棵树的所有边中，具有最小权值的边，如果将它加入生成树中不产生回路，则它就是生成树中的一条边。这里的关键就是如何判断"将它加入生成树中不产生回路"。

《算法导论》提供的一种方法是采用一种"不相交集合数据结构"，也就是并查集。核心内容是如果某两个节点（判断他们的根节点是不是一个，如果是一个根节点，那么把这两个点连接起来，就会形成回路）属于同一棵树(Find_Set)，那么将它们合并(Union)后一定会形成回路。

首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。

至于怎么合并到一个集合，那么这里我们就可以用到一个工具——-并查集。（之后会提到）

换而言之，Kruskal算法就是基于并查集的贪心算法。

二、Kruskal算法思想：

Kruskal算法将每一个顶点都初始化为一棵树，并定义一棵MST树用来存储每次合并后的图结构。每次循环寻找权重最小的边，如果这条边的添加不会形成回路，那么在MST树中添加相应的边。如果这条边添加后会在MST中形成回路，那么忽略这条边。当所有边都被检索完毕后，结束算法退出循环。

具体流程：
(1)将图G看做一个森林，每个顶点为一棵独立的树
(2)将所有的边加入集合S，即一开始S = E
(3)从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E'
(4)重复(3)直到所有点属于同一棵树，边集E'就是一棵最小生成树

我们用现在来模拟一下Kruskal算法，下面给出一个无向图B,我们使用Kruskal来找无向图B的最小生成树。

首先，我们将所有的边都进行从小到大的排序。排序之后根据贪心准则，我们选取最小边(A,D)。我们发现顶点A,D不在一棵树上，所以合并顶点A,D所在的树，并将边(A,D)加入边集E‘。

我们接着在剩下的边中查找权值最小的边，于是我们找到的(C,E)。我们可以发现，顶点C,E仍然不在一棵树上，所以我们合并顶点C，E所在的树，并将边(C,E)加入边集E'

不断重复上述的过程，于是我们就找到了无向图B的最小生成树，如下图所示：

三、并查集

（此部分转载于知乎 Pecco作者的算法学习笔记（1）：并查集）

并查集的两个作用：

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

并查集的引入

并查集的重要思想在于，用集合中的一个元素代表集合。我曾看过一个有趣的比喻，把集合比喻成帮派，而代表元素则是帮主。接下来我们利用这个比喻，看看并查集是如何运作的。

preview

最开始，所有大侠各自为战。他们各自的帮主自然就是自己。（对于只有一个元素的集合，代表元素自然是唯一的那个元素）

现在1号和3号比武，假设1号赢了（这里具体谁赢暂时不重要），那么3号就认1号作帮主（合并1号和3号所在的集合，1号为代表元素）。

preview

现在2号想和3号比武（合并3号和2号所在的集合），但3号表示，别跟我打，让我帮主来收拾你（合并代表元素）。不妨设这次又是1号赢了，那么2号也认1号做帮主。

preview

现在我们假设4、5、6号也进行了一番帮派合并，江湖局势变成下面这样：

preview

现在假设2号想与6号比，跟刚刚说的一样，喊帮主1号和4号出来打一架（帮主真辛苦啊）。1号胜利后，4号认1号为帮主，当然他的手下也都是跟着投降了。

preview

如果你有一点图论基础，相信你已经觉察到，这是一个树状的结构，要寻找集合的代表元素，只需要一层一层往上访问父节点（图中箭头所指的圆），直达树的根节点（图中橙色的圆）即可。根节点的父节点是它自己。我们可以直接把它画成一棵树：

用这种方法，我们可以写出最简单版本的并查集代码。

初始化


int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

假如有编号为1, 2, 3, ..., n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。

查询


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

我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

合并


inline void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。本文末尾会给出一个更合理的比较方法。

路径压缩

最简单的并查集效率是比较低的。例如，来看下面这个场景：

现在我们要merge(2,3)，于是从2找到1，fa[1]=3，于是变成了这样：

然后我们又找来一个元素4，并需要执行merge(2,4)：

从2找到1，再找到3，然后fa[3]=4，于是变成了这样：

其实这说来也很好实现。只要我们在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，我们就可以省很多事。这用递归的写法很容易实现：

合并（路径压缩）


int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

大家应该有感觉了，这样可能会形成一条长长的链，随着链越来越长，我们想要从底部找到根节点会变得越来越难。

怎么解决呢？我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步，像这样：

合并（路径压缩）


int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

以上代码常常简写为一行：


int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

注意赋值运算符=的优先级没有三元运算符?:高，这里要加括号。

路径压缩优化后，并查集的时间复杂度已经比较低了，绝大多数不相交集合的合并查询问题都能够解决。然而，对于某些时间卡得很紧的题目，我们还可以进一步优化。

按秩合并

有些人可能有一个误解，以为路径压缩优化后，并查集始终都是一个菊花图（只有两层的树的俗称）。但其实，由于路径压缩只在查询时进行，也只压缩一条路径，所以并查集最终的结构仍然可能是比较复杂的。例如，现在我们有一棵较复杂的树需要与一个单元素的集合合并：

假如这时我们要merge(7,8)，如果我们可以选择的话，是把7的父节点设为8好，还是把8的父节点设为7好呢？

当然是后者。因为如果把7的父节点设为8，会使树的深度（树中最长链的长度）加深，原来的树中每个元素到根节点的距离都变长了，之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩，但路径压缩也是会消耗时间的。而把8的父节点设为7，则不会有这个问题，因为它没有影响到不相关的节点。

这启发我们：我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。

我们用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。

路径压缩和按秩合并如果一起使用，时间复杂度接近

转存失败重新上传取消，但是很可能会破坏rank的准确性。

初始化（按秩合并）


inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

合并（按秩合并）


inline void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

为什么深度相同，新的根节点深度要+1？如下图，我们有两个深度均为2的树，现在要merge(2,5)：

这里把2的父节点设为5，或者把5的父节点设为2，其实没有太大区别。我们选择前者，于是变成这样：

显然树的深度增加了1。另一种合并方式同样会让树的深度+1。

并查集的应用

题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入格式
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出格式
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

这其实是一个很有现实意义的问题。我们可以建立模型，把所有人划分到若干个不相交的集合中，每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚，只需看它们是否属于同一个集合即可。因此，这里就可以考虑用并查集进行维护了。

我们先给出亲戚问题的AC代码：


#include <cstdio>
#define MAXN 5005
int fa[MAXN], rank[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
}
int main()
{
    int n, m, p, x, y;
    scanf("%d%d%d", &n, &m, &p);
    init(n);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d", &x, &y);
        merge(x, y);
    }
    for (int i = 0; i < p; ++i)
    {
        scanf("%d%d", &x, &y);
        printf("%s\n", find(x) == find(y) ? "Yes" : "No");
    }
    return 0;
}

四、关于qsort函数

qsort函数的用法说明如下：

qsort函数包含在stdlib.h头文件里,函数一共四个参数,没返回值.

一个典型的qsort的写法如下：qsort(s,n,sizeof(s[0]),cmp);

第一个参数是参与排序的数组名(或者也可以理解成开始排序的地址,因为可以写&s[i]
这样的表达式,这个问题下面有说明)

第二个参数是参与排序的元素个数;

第三个参数是单个元素的大小,推荐使用sizeof(s[0])这样的表达式

第四个参数是比较函数

例：qsort(a,1000,sizeof(int),cmp);

五、qsort函数中第四个参数：cmp函数

int cmp(const void a, const void b)

cmp函数应写为：

int cmp(const void*a,const void*b)

{

return *(int*)a-*(int*)b;

}

上面是由小到大排序

return *(int *)b - *(int *)a; 为由大到小

返回值必须是int,两个参数的类型必须都是const void *。

假设是对int排序的话,如果是升序,那么就是如果a比b大，返回一个正值。小则负值,相等返回0

本程序中


int cmp(const void* a, const void* b)//比较大小 
//声明cmp函数，其返回值为int型，参数为两个不可修改的void型指针
//如果是const void*的话，意思就是使用指针，通过引用传递，避免了值传递时的性能代价，使用const的话，就是确保这个值在整个函数的执行过中，不会改变所上面两个参数的值。
{
	if ((*(edge*)a).weight == (*(edge*)b).weight)
	{
		return (*(edge*)a).x - (*(edge*)b).x;
	}
	return (*(edge*)a).weight - (*(edge*)b).weight;
}

qsort(e, n, sizeof(edge), cmp);//调用qsort函数

六、代码实现：


#include<stdio.h>
#include<stdlib.h>
#define Max 20
int sum = 0;//定义sum，返回构建完成的MST的最短路径长度
typedef struct//在此定义了一个关于边的结构体类型
{
	int x, y;//意思是一条边的两个顶点为 x,y
	int weight;//边的权值
}edge;
edge e[Max];//定义了一个e数组，里面存放的是输入（后续会经过排序，按从小到大的顺序排列）的边
int rank[Max];//为了压缩路径，通过比较秩，目的是得到一颗深度尽可能小的MST
int father[Max];//father[x]是表示 寻找顶点x的父节点，往上找一个
 
void Init(int n)//对点进行初始化
{
	for (int i = 1;i <= n;i++)
	{
		father[i] = i;//先使得输入的各点各成一棵树，这样的话，输入所有的顶点可以看作一个森林，有n个树
		//kruskal算法就是把这n棵树连成一棵树
		rank[i] = 0;
	}
}
int find(int i)//去找根节点，方便进行后续根节点之间的比比较
{
	if (father[i] == i)
		return i;
	else
	{
		father[i] = find(father[i]);//递归
		return father[i];
	}
}
void Union(int x, int y)//通过秩的比较，进行路径压缩
{
	if (x == y) return;
	if (rank[x] < rank[y]) father[x] = y;
	if (rank[x] > rank[y]) father[y] = x;
	if (rank[x] == rank[y])
	{
		rank[y]++;
		father[x] = y;
	}
}
int cmp(const void* a, const void* b)//比较大小 
//声明cmp函数，其返回值为int型，参数为两个不可修改的void型指针
//如果是const void*的话，意思就是使用指针，通过引用传递，避免了值传递时的性能代价，使用const的话，就是确保这个值在整个函数的执行过中，不会改变所上面两个参数的值。
{
	if ((*(edge*)a).weight == (*(edge*)b).weight)
	{
		return (*(edge*)a).x - (*(edge*)b).x;
	}
	return (*(edge*)a).weight - (*(edge*)b).weight;
}
 
int Kruskal(int n, int m)//输入n个顶点,m条边
{
	for (int i = 1;i <= n;i++)//对点进行初始化 
	{
		Init(n);
	}
	for (int i = 1;i <= m;i++)
	{
		printf("请输入第%d条边对应的两个顶点与权值:",i);
		scanf_s("%d,%d,%d", &e[i].x, &e[i].y, &e[i].weight);
	}
	qsort(e, n, sizeof(edge), cmp);
	for (int i = 1;i <= m;i++)
	{
		int xx, yy;
		xx = find(e[i].x);
		yy = find(e[i].y);
		if (xx != yy)//当现在找到的两个顶点的根节点不同，说明这两个点可以进行连接
		{
			printf("点%d <--> 点%d = %d\n", e[i].x, e[i].y, e[i].weight);
			Union(xx, yy);//使目前可以连接的两个顶点的根节点保持一样
			sum += e[i].weight;//每找到一条路景，就刷新最短路径长度
		}
	}
	return sum;
}
 
int main()
{
	int n, m, summ;
	printf("请输入顶点数和边数:");
	scanf_s("%d,%d", &n, &m);
	summ = Kruskal(n, m);//调用kruskal算法
	printf("构建的最小生成树的最短路径长度为%d", sum);
	return 0;
}

实现结果：（将图中ABCD字母转化为1234等数字输入）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/131028