Kruskal 最小生成树算法

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode 力扣 难度
1135. Connecting Cities With Minimum Cost🔒 1135. 最低成本联通所有城市🔒 🟠
1584. Min Cost to Connect All Points 1584. 连接所有点的最小费用 🟠
261. Graph Valid Tree🔒 261. 以图判树🔒 🟠

———–

图论中知名度比较高的算法应该就是 Dijkstra 最短路径算法环检测和拓扑排序二分图判定算法 以及今天要讲的最小生成树(Minimum Spanning Tree)算法了。

最小生成树算法主要有 Prim 算法(普里姆算法)和 Kruskal 算法(克鲁斯卡尔算法)两种,这两种算法虽然都运用了贪心思想,但从实现上来说差异还是蛮大的。

本文先来讲比较简单易懂的 Kruskal 算法,然后在下一篇文章 Prim 算法模板 中聊 Prim 算法。

Kruskal 算法其实很容易理解和记忆,其关键是要熟悉并查集算法,如果不熟悉,建议先看下前文 Union-Find 并查集算法

接下来,我们从最小生成树的定义说起。

什么是最小生成树

先说「树」和「图」的根本区别:树不会包含环,图可以包含环

如果一幅图没有环,完全可以拉伸成一棵树的模样。说的专业一点,树就是「无环连通图」。

那么什么是图的「生成树」呢,其实按字面意思也好理解,就是在图中找一棵包含图中的所有节点的树。专业点说,生成树是含有图中所有顶点的「无环连通子图」。

容易想到,一幅图可以有很多不同的生成树,比如下面这幅图,红色的边就组成了两棵不同的生成树:

对于加权图,每条边都有权重,所以每棵生成树都有一个权重和。比如上图,右侧生成树的权重和显然比左侧生成树的权重和要小。

那么最小生成树很好理解了,所有可能的生成树中,权重和最小的那棵生成树就叫「最小生成树」

一般来说,我们都是在无向加权图中计算最小生成树的,所以使用最小生成树算法的现实场景中,图的边权重一般代表成本、距离这样的标量。

在讲 Kruskal 算法之前,需要回顾一下 Union-Find 并查集算法。

_____________

应合作方要求,本文不便在此发布,请扫码关注回复关键词「生成树」或 点这里 查看:

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释