图论- 经典最小天生树算法

什么是最小天生树

在图中找一棵包罗图中全部节点的树, 且权重和最小的那棵树就叫最小天生树.
如下:右侧天生树的权重和显然比左侧天生树的权重和要小。(但是它并不是最小的,这里只是比较一下不同的树)

Kruskal算法

最小天生树是多少条边的集合(称为mst)
最小天生树中我们必要保证几点:

• 包罗图中全部节点
  
• 形成的布局是树布局(不存在环)
  
• 权重和最小
  前面两条很容易利用并查集算法做到
  最后一条这里使用了贪婪算法的头脑:
  将全部边按照权重从小到大排序,从权重最小的边开始遍历,如果这条边和mst中其他边不形成边,则称为mst的一部门,否则不加入.
  

关键代码实现

想学好这个算法有两个关键的点:

• 熟悉掌握并查集算法,对于判断是否成环和连通分量如何盘算要熟悉
  
• 清楚贪婪头脑和最后如何累积权重并返回.
  

1. [/code] [size=4]Prim 最小天生树算法[/size]
3. 它也是使用贪婪头脑来让天生树的权重尽可能小,它接纳切分的方式去处置处罚.
4. 简单来说呢就是从一个节点开始,看这个节点有几条路径,然后选一条最短.
5. 走到下一个节点的时候,同时考虑之前的节点的路径,然后选一条最短的,然后循环这样.
6. 举例:
7. [align=center][img]https://i-blog.csdnimg.cn/direct/8ac0d591cd11421a9b09be3381b092d1.png[/img][/align]
8. 这里固然是在B节点,但是也要考虑A节点的情况.
9. Prim 算法的逻辑就是这样，每次切分都能找到最小天生树的一条边，然后又可以举行新一轮切分，直到找到最小天生树的全部边为止。
10. 那代码如何实现呢?
11. 我们如何盘算横切边有哪些,好比是否可以快速算出 cut({A, B, C})，也就是节点 A, B, C 的全部「横切边」有哪些？
12. [align=center][img]https://i-blog.csdnimg.cn/direct/d3b827feba7b4f75a8e01999213ac4f2.png[/img][/align]
13. 是可以的,因为我们发现:
14.   cut({A, B, C}) = cut({A, B}) + cut({C})
15. [align=center][img]https://i-blog.csdnimg.cn/direct/6201b91b2c92426da97e5adf377787be.png[/img][/align]
16. 这个特点使我们用我们写代码实现「切分」和处置处罚「横切边」成为可能：
17. 在举行切分的过程中，我们只要不断把新节点的邻边加入横切边集合，就可以得到新的切分的全部横切边。
18. 当然，细心的你肯定发现了，cut({A, B}) 的横切边和 cut({C}) 的横切边中 BC 边重复了。
19. 不外这很利益理，用一个布尔数组 inMST 辅助，防止重复盘算横切边就行了。
20. 最后一个题目，我们求横切边的目的是找权重最小的横切边，怎么做到呢？
21. 很简单，用一个
22. 优先级队列 存储这些横切边，就可以动态盘算权重最小的横切边了。
23. 所以接纳inMST和优先级队列可以帮助我们实现这个算法.
24. 实现如下:
25. [code]class Prim {
26.     // 核心数据结构，存储「横切边」的优先级队列
27.     private PriorityQueue<int[]> pq;
28.     // 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分
29.     private boolean[] inMST;
30.     // 记录最小生成树的权重和
31.     private int weightSum = 0;
32.     // graph 是用邻接表表示的一幅图，
33.     // graph[s] 记录节点 s 所有相邻的边，
34.     // 三元组 int[]{from, to, weight} 表示一条边
35.     private List<int[]>[] graph;
37.     public Prim(List<int[]>[] graph) {
38.         this.graph = graph;
39.         this.pq = new PriorityQueue<>((a, b) -> {
40.             // 按照边的权重从小到大排序
41.             return a[2] - b[2];
42.         });
43.         // 图中有 n 个节点
44.         int n = graph.length;
45.         this.inMST = new boolean[n];
47.         // 随便从一个点开始切分都可以，我们不妨从节点 0 开始
48.         inMST[0] = true;
49.         cut(0);
50.         // 不断进行切分，向最小生成树中添加边
51.         while (!pq.isEmpty()) {
52.             int[] edge = pq.poll();
53.             int to = edge[1];
54.             int weight = edge[2];
55.             if (inMST[to]) {
56.                 // 节点 to 已经在最小生成树中，跳过
57.                 // 否则这条边会产生环
58.                 continue;
59.             }
60.             // 将边 edge 加入最小生成树
61.             weightSum += weight;
62.             inMST[to] = true;
63.             // 节点 to 加入后，进行新一轮切分，会产生更多横切边
64.             cut(to);
65.         }
66.     }
68.     // 将 s 的横切边加入优先队列
69.     private void cut(int s) {
70.         // 遍历 s 的邻边
71.         for (int[] edge : graph[s]) {
72.             int to = edge[1];
73.             if (inMST[to]) {
74.                 // 相邻接点 to 已经在最小生成树中，跳过
75.                 // 否则这条边会产生环
76.                 continue;
77.             }
78.             // 加入横切边队列
79.             pq.offer(edge);
80.         }
81.     }
83.     // 最小生成树的权重和
84.     public int weightSum() {
85.         return weightSum;
86.     }
88.     // 判断最小生成树是否包含图中的所有节点
89.     public boolean allConnected() {
90.         for (int i = 0; i < inMST.length; i++) {
91.             if (!inMST[i]) {
92.                 return false;
93.             }
94.         }
95.         return true;
96.     }
97. }

复制代码

Kruskal 和 Prim 算法的区别

特点Kruskal算法Prim算法处置处罚方式从边出发，选择最小的边加入天生树从一个节点出发，逐步扩展天生树实用图的类型适当稀疏图适当稠密图数据布局使用并查集来检测环，处置处罚边集合使用优先队列（最小堆）来选择最小边时间复杂度(O(E \log E))(O(E \log V))边的处置处罚方式对全部边举行排序按节点扩展，逐步选择最小边图的表示方式边列表毗邻矩阵或毗邻表 为什么Prim算法不必要判断成环,但Kruskal必要

Kruskal算法必要查抄是否会成环，因为它是从全局边集合出发逐步加入边，必要判断两个节点是否已经连通。
Prim算法不必要显式查抄环，因为它是从节点逐步扩展天生树的过程，保证了每次连接的边都是新增的，不会成环。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。