跳至主要內容

 

labuladong约 925 字大约 3 分钟数据结构图论算法

Info

算法可视化编辑器上线,点击体验open in new window

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

LeetCode力扣难度
1135. Connecting Cities With Minimum Costopen in new window🔒1135. 最低成本联通所有城市open in new window🔒🟠
1584. Min Cost to Connect All Pointsopen in new window1584. 连接所有点的最小费用open in new window🟠

本文是第 7 篇图论算法文章,先列举一下我之前写过的图论算法:

1、图论算法基础

2、二分图判定算法

3、环检测和拓扑排序算法

4、Dijkstra 最短路径算法

5、Union Find 并查集算法

6、Kruskal 最小生成树算法

像图论算法这种高级算法虽然不算难,但是阅读量普遍比较低,我本来是不想写 Prim 算法的,但考虑到算法知识结构的完整性,我还是想把 Prim 算法的坑填上,这样所有经典的图论算法就基本完善了。

Prim 算法和 Kruskal 算法都是经典的最小生成树算法,阅读本文之前,希望你读过前文 Kruskal 最小生成树算法,了解最小生成树的基本定义以及 Kruskal 算法的基本原理,这样就能很容易理解 Prim 算法逻辑了。

对比 Kruskal 算法

图论的最小生成树问题,就是让你从图中找若干边形成一个边的集合 mst,这些边有以下特性:

1、这些边组成的是一棵树(树和图的区别在于不能包含环)。

2、这些边形成的树要包含所有节点。

3、这些边的权重之和要尽可能小。

那么 Kruskal 算法是使用什么逻辑满足上述条件,计算最小生成树的呢?

首先,Kruskal 算法用到了贪心思想,来满足权重之和尽可能小的问题:

先对所有边按照权重从小到大排序,从权重最小的边开始,选择合适的边加入 mst 集合,这样挑出来的边组成的树就是权重和最小的。

其次,Kruskal 算法用到了 Union-Find 并查集算法,来保证挑选出来的这些边组成的一定是一棵「树」,而不会包含环或者形成一片「森林」:

如果一条边的两个节点已经是连通的,则这条边会使树中出现环;如果最后的连通分量总数大于 1,则说明形成的是「森林」而不是一棵「树」。

那么,本文的主角 Prim 算法是使用什么逻辑来计算最小生成树的呢?

首先,Prim 算法也使用贪心思想来让生成树的权重尽可能小,也就是「切分定理」,这个后文会详细解释。

其次,Prim 算法使用 BFS 算法思想visited 布尔数组避免成环,来保证选出来的边最终形成的一定是一棵树。

Prim 算法不需要事先对所有边排序,而是利用优先级队列动态实现排序的效果,所以我觉得 Prim 算法类似于 Kruskal 的动态过程。

下面介绍一下 Prim 算法的核心原理:切分定理。

加载中...