code前端网图论算法 Prim算法：与Kruskal算法的比较、分割定理、实现与实践问题
Prim算法和Kruskal算法都是经典的最小生成树算法。在阅读本文之前，希望您了解Kruskal最小生成树的基本定义以及Kruskal算法的基本原理，以便您能够轻松理解Prim算法的逻辑。
对比Kruskal的算法
图论的最小生成树问题可以让你从一个图中找到边的数量，从而形成一组边mst。这些边有以下特点：
1，这些边形成一棵树（树和图的区别在于它们不能包含环）。
2。由这些边形成的树必须包含所有节点。
3。这些边的权重之和应尽可能小。
那么Kruskal的算法是用什么样的逻辑来满足上述条件并计算出最小生成树呢？
首先，Kruskal的算法使用贪心思想来解决保持权重之和尽可能小的问题：
首先，将所有边按照权重从小到大排序，从有边的边开始重量最小的，然后选择合适的。将边添加到集合 mst 中，以便由所选边组成的树具有最小的权重总和。
其次，Kruskal的算法使用并查算法来确保所选边必须形成“树”，并且不会包含循环或形成“森林”：
如果两条是节点边已经连通，这条边会造成树中出现环路；如果最终连通分量总数大于1，则说明形成的不是“树”而是“森林” Tree
那又怎样本文主角Prim的算法是用什么逻辑来计算最小生成树的？
首先，Prim的算法还利用了贪心思维，让生成树的权重尽可能小，这是一个“
其次，Prim算法利用BFS算法和访问逻辑字符串避免循环保证选择的边最终必须形成一棵树，需要对所有边进行预先排序，但是使用优先级队列来动态实现排序效果，所以我认为Prim算法类似于Kruskal的动态过程。
我们介绍 Prim 算法的基本原理：分割定理
分割定理
“分割”这个词其实很容易理解，就是将一幅图像分割成两个不重叠的部分 且节点是非空的集合：
红刀将图中的节点分割成两个集合，这是一种“分割”，其中边被红线（以蓝色突出显示）切割的称为“交叉边缘”。
PS：记住这两个专业术语的含义。我们稍后会经常使用这两个词，所以不要被愚弄。
当然，一张图像肯定可以有多种分割方式，因为根据分割的定义，只要一笔就能将一个节点分割成两部分。
然后我们引入“分割定理”：
对于任何“分割”，最小权重的“横向边”必须是形成最小生成树的边。
这应该很容易证明。如果带权无向图有一棵最小生成树，假设下图中绿色标记的边是一棵最小生成树： 
那么你一定可以找到一个多“割”的方法，将这棵最小生成树分割成两个子树。比如下面的分割： 
你会发现任何蓝色的“横边”都可以连接两棵子树，形成一棵生成树。
那么如何选择才能减少最终夹紧的树的总重量呢？
你必须选择重量最轻的“十字边”，对吗？这由分割定理证明。
至于分割定理，也可以通过反证法来证明：
给定一个图的最小生成树，即给定任何“分割”，都必须有至少一个“横向边”属于最小生成树 Tree 。
假设这条“横边”不是权重最小的边，这意味着最小生成树的权重之和可以减少。那么就矛盾了。最小生成树的权重之和已经是最小的。如何减少呢？所以分割定理是正确的。
有了这个划分定理，你可能已经有了计算最小生成树的算法思想：
因为每次“切割”肯定能在最小生成树中找到一条边，所以我就将它切割并取“每次权重最小的“横向边”，将其添加到最小生成树中，直到构成最小生成树的所有边都被切断。
嗯，可以说这就是Primo算法的核心思想，但是具体实现还是需要一些技巧的。
既然你无法让计算机理解“随意切片”的含义，那么你应该设计机械化的规则和规定来训练你的算法并最大限度地减少浪费的精力。
Prim算法实现
在思考算法问题时，如果问题的一般情况很难解决，我们可以从相对简单的特殊情况开始。这就是算法Cf所使用的思想。
根据“割”的定义，只要将图中的节点割成两组不重叠且非空的节点，这就可以认为是合法的“割” ，那么只有剪裁一个节点才算合法的“段”吗？
是的，这就是最简单的“分割”，“横向边”也很容易确定，就是这个节点的边。
然后我们就随机选择一个点，假设我们从点A开始分割： 
既然这是合法的“分割”，根据分割定理，这些“相交” -切割“边中权重最小的Rob”AB，AF一定是最小生成树中的一条边：
好了，现在我们找到了最小生成树的第一条边（边AB），那么接下来的“分割”该如何安排呢？
根据Prim算法的逻辑，我们就可以分割两个节点A和B：
然后我们可以从这个分割中创建一个水平分割，找到切边中权重最小的边（图中蓝色边），然后在最小生成树中找到另一条边BC：
接下来呢？这个也类似，如果我们把它分成三点A，B，C，生成的交叉边中权重最小的边是BD，那么BD就是最小生成树的第三条边：
然后围绕四个点A，B，C，D...
Prim算法的逻辑是这样，每个分叉都可以找到最小生成树的边，然后可以进行新一轮的分裂，直到最小生成树的所有边都找到这棵树 。
以这种方式设计算法的优点之一是更容易确定每个新“分割”创建的“相交锐度”。
例如，只要回头看图，就知道节点A, B的所有“交叉边”（或许表示为 cut({A, B} ) ），就是图中的蓝色边缘：
你能快速计算出cut({A, B, C})，即所有节点A,B,C什么是“横向边缘”？
是可能的，因为我们发现：
cut({A, B, C}) = cut({A, B}) + cut({C})
和cut({C})都是节点C：
这个函数允许我们使用它可以编写代码实现“分割”，处理“横边”：
在切割过程中，我们只需要将新节点的相邻边不断添加到横边集合中，就可以得到所有横边的新线段。
当然，细心的读者一定发现了，横边cut({A, B})和横边cut({C})BC重复。
但是很容易处理。只需使用 MST 中的布尔矩阵 最后一个问题，我们求交叉边的目的是找到权重最小的交叉边。怎么做？ 非常简单。使用优先级队列来存储这些交叉边，您可以动态计算权重最小的交叉边。 了解了上面算法的原理，我们来看看Prim算法的代码实现： 理解了分割定理，加上详细的代码注释，你应该能看懂Prim算法的代码了。 这里我们可以回顾一下本文开头提到的Prim算法和Kruskal算法之间的联系： Kruskal算法一开始对所有边进行排序，然后选择最小的代，从权重最小的边开始。树的边形成最小生成树。 Prim 的算法从一个起点（一组交叉边）开始，执行类似于 BFS 算法的逻辑。利用切割定理和优先级队列的动态排序特性，从这个起点“生长”出一棵最小树。被夹住的树。 说到这里，Prim算法的时间复杂度是多少？ 这个不难分析。复杂度主要在于优先级队列 因此，Prim 算法实现的总时间复杂度为 与之前的Dijkstra算法类似，Prim算法的时间复杂度也可以进行优化，但是优化的点在于优先级队列的实现上，与算法思想关系不大Prim算法本身，所以这里不讨论，有兴趣的读者可以自行搜索。 然后我们做一些实际工作，用Primo的算法来解决Likou问题，这个问题之前是用Kruskal的算法解决的。 第一题完全按照1135题“最低价格连接所有城市”。这是标准的最小生成树问题： 函数的签名如下： 每个站点都是等效的 对于图中的节点，连接站点的成本相当于边的权重。连接所有城市的最小成本是最小生成树的权重之和。 那么解决方案就显而易见了。问题中输入的 需要注意的两点 首先问题中给出的节点号是从1开始的，所以我们偏移索引，转换为从0开始，所以 第二个是如何使用邻接表来表示无向加权图。正如上一篇文章《图论算法基础》中提到的，“无向图”实际上可以认为是“双向图”。 这样，我们变换后的形状 让我们看一下Likou问题1584“连接所有点的最小成本”： 例如问题中给出的示例： 算法应返回20并按如下方式连接点： 函数签名如下： 显然，这也是一个标准的最小生成树问题：每个点都是无向加权图中的一个节点，边权重是曼哈顿距离，连接所有点的最小成本是最小生成树权重之和。 所以我们只需要将矩阵 这题有小解：每个坐标点都是元组，所以用五元组来表示加权边是合乎逻辑的，但在这种情况下实现Prim的算法是不合适的；所以我们用矩阵 作者：labuladong 即可避免重新计算交叉边。class Prim {
// 核心数据结构，存储「横切边」的优先级队列
private PriorityQueue<int[]> pq;
// 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分
private boolean[] inMST;
// 记录最小生成树的权重和
private int weightSum = 0;
// graph 是用邻接表表示的一幅图，
// graphSpread收缩 记录节点 s 所有相邻的边，
// 三元组 int[]{from, to, weight} 表示一条边
private List<int[]>[] graph;
public Prim(List<int[]>[] graph) {
this.graph = graph;
this.pq = new PriorityQueue<>((a, b) -> {
// 按照边的权重从小到大排序
return a[2] - b[2];
});
// 图中有 n 个节点
int n = graph.length;
this.inMST = new boolean[n];
// 随便从一个点开始切分都可以，我们不妨从节点 0 开始
inMST[0] = true;
cut(0);
// 不断进行切分，向最小生成树中添加边
while (!pq.isEmpty()) {
int[] edge = pq.poll();
int to = edge[1];
int weight = edge[2];
if (inMST[to]) {
// 节点 to 已经在最小生成树中，跳过
// 否则这条边会产生环
continue;
}
// 将边 edge 加入最小生成树
weightSum += weight;
inMST[to] = true;
// 节点 to 加入后，进行新一轮切分，会产生更多横切边
cut(to);
}
}
// 将 s 的横切边加入优先队列
private void cut(int s) {
// 遍历 s 的邻边
for (int[] edge : graphSpread收缩) {
int to = edge[1];
if (inMST[to]) {
// 相邻接点 to 已经在最小生成树中，跳过
// 否则这条边会产生环
continue;
}
// 加入横切边队列
pq.offer(edge);
}
}
// 最小生成树的权重和
public int weightSum() {
return weightSum;
}
// 判断最小生成树是否包含图中的所有节点
public boolean allConnected() {
for (int i = 0; i < inMST.length; i++) {
if (!inMST[i]) {
return false;
}
}
return true;
}
}
pq的操作。由于pq在图中包含“边”，假设图的边为Number of Entries E，则最大操作为O(E)次pq。优先级队列中每个操作的时间复杂度取决于队列中元素的数量。最糟糕的情况是 O(logE)。 O(ElogE)。回想一下Kruskal的算法，它的时间复杂度主要是对所有边按照权重进行排序，也是O(ElogE)。 练习题
int minimumCost(int n, int[][] connections);
连接首先转换为邻接表形式，然后输入到之前实现的算法类中Prim：public int minimumCost(int n, int[][] connections) {
// 转化成无向图邻接表的形式
List<int[]>[] graph = buildGraph(n, connections);
// 执行 Prim 算法
Prim prim = new Prim(graph);
if (!prim.allConnected()) {
// 最小生成树无法覆盖所有节点
return -1;
}
return prim.weightSum();
}
List<int[]>[] buildGraph(int n, int[][] connections) {
// 图中共有 n 个节点
List<int[]>[] graph = new LinkedList[n];
for (int i = 0; i < n; i++) {
graph[i] = new LinkedList<>();
}
for (int[] conn : connections) {
// 题目给的节点编号是从 1 开始的，
// 但我们实现的 Prim 算法需要从 0 开始编号
int u = conn[0] - 1;
int v = conn[1] - 1;
int weight = conn[2];
// 「无向图」其实就是「双向图」
// 一条边表示为 int[]{from, to, weight}
graph[u].add(new int[]{u, v, weight});
graph[v].add(new int[]{v, u, weight});
}
return graph;
}
class Prim { /* 见上文 */ }
buildGraph函数：Prim使用class； graph就对应了算法的上一类Prim，可以直接使用Prim算法来计算最小生成树。 
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
int minCostConnectPoints(int[][] points);
点转换为邻接表形式，然后就可以复用之前实现的算法类Comp：public int minCostConnectPoints(int[][] points) {
int n = points.length;
List<int[]>[] graph = buildGraph(n, points);
return new Prim(graph).weightSum();
}
// 构造无向图
List<int[]>[] buildGraph(int n, int[][] points) {
List<int[]>[] graph = new LinkedList[n];
for (int i = 0; i < n; i++) {
graph[i] = new LinkedList<>();
}
// 生成所有边及权重
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int xi = points[i][0], yi = points[i][1];
int xj = points[j][0], yj = points[j][1];
int weight = Math.abs(xi - xj) + Math.abs(yi - yj);
// 用 points 中的索引表示坐标点
graph[i].add(new int[]{i, j, weight});
graph[j].add(new int[]{j, i, weight});
}
}
return graph;
}
class Prim { /* 见上文 */ }
points中的索引来表示。对于每个坐标点，可以直接复用之前Prim算法的逻辑。
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
