最小生成树(MTS)之Kruskal算法

vlambda
2022-04-17

最小生成树(MTS)之Kruskal算法

Kruskal 算法是最小生成树（minimum spanning tree ）的经典算法之一。这是个很努力的算法，不放弃任何一个可能的机会，尝试了每一条边。成环不会阻挠它前进的脚步，不紧不慢不卑不亢，最终带给我们人类一个满意的结果。虽然不是MST中最聪明的，但却是很可爱的

B站UP主Compsyc计算之心

常见的数据结构中树的应用较多一些，在树的节点关系中称之为父子关系，而在一些特定场景下图能更清晰表达。

Graph图的基本概念

在图中，右每一个顶点和边路径构成，顶点与顶点之间我们称之为朋友关系，因为不仅仅有一条路径，图中每个顶点有几条边，即为度，如果在图中路径是有方向的，那么称之为有向图，有向图中被指向叫做入度，指向叫做出度。顶点之间的距离称之为权重。

最小生成树

一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树：minimum spanning tree 在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

最短路径问题

简单地说，就是给定一组点，给定每个点间的距离，求出点之间的最短路径。

路径问题大概有以下几种：

确定起点的最短路径问题：已知起始点，求起点到其他任意点最短路径的问题。即单源最短路径问题。
确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终点，求最短路径的问题。在无向图（即点之间的路径没有方向的区别）中该问题与确定起点的问题完全等同，在有向图（路径间有确定的方向）中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题：已知起点和终点，求任意两点之间的最短路径。即多源最短路径问题。
指定起点遍历所有节点的最短路径问题：已知起点，求从起点走过所有端点的最短路径问题。

常见算法

由于翻译问题我们用英文表示

1.Bellman-Ford

2.Dijkstra

3.Floyd

4.TSP(禁忌算法)

5.贪心算法

好,我们接着上篇的送外卖问题，慢慢引出这几个问题，先补充下上篇文中的错误，原文如下

应用场景

当前外卖骑手接单N单，如何计划路线才是最优配送路线？

思路：

先计算N单客户距离配送商户距离，起点固定为商户，终点为客户，然后比较N个路线中距离从小到大排列，即为最优路线。
枚举出商户到客户的全排列，计算出每个路线的距离，这一次与上一次的距离比较，哪个路线最小保留。

这里的第一个场景计算逻辑是错误的，我们只考虑到了单次送达客户的距离，并没有考虑到客户到客户之间的距离，比如下面这种情况

如图

假设我们送达是按着先送C，再送B，然后送A的话，按着我们的思路除非这三个客户在同一个方向，否则这种不考虑客户距离的送法是不合理的，那么真实的送货路线就变成了

最小生成树(MTS)之Kruskal算法

这样实际的公里数是60km,而我们第一种场景的理论公里数是45km。

那么我们第二种暴力方法适合吗？又适用于哪种算法呢？

全排列的算法固然能考虑到每种方案，但是效率就过低了。

为什么不先介绍Bellman-Ford和Dijkstra算法？

首先Dijkstra用于计算一个节点到其他节点（不是所有节点到所有节点）的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想BSF)，直到扩展到终点为止，不适合当前场景。

而Bellman-Ford适用于计算单源最短路径，而不是走遍所有节点，也不适合。

Kruskal算法

‍求加权连通图的最小生成树。‍

1.所有权重从小到大排列

2.不能形成回环

示例

最小生成树(MTS)之Kruskal算法来自B站UP主Compsyc计算之心

先列举权重排列

最小生成树(MTS)之Kruskal算法

如何防止回环？

每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路

感谢B站UP主Compsyc计算之心精心制作的算法解题视频，第一次刷到此视频就被其生动的文案所打动，视频风格和制作都很用心，推荐大家关注。

废话不多说让我们观赏下原视频

已关注

Replay Share Like

赵KK日常技术记录

Added to Top Stories

0/0

00:00 / 02:10

全屏

倍速播放中

继续观看

最小生成树(MTS)之Kruskal算法

赵KK日常技术记录

Added to Top Stories

【Kruskal算法之通用版 | 最小生成树MST | 无代码可视化纯享版-哔哩哔哩】 https://b23.tv/o35bzQ

我也自己参考做了几张图

最小生成树(MTS)之Kruskal算法

每次开始筛选最小边路径，然后在符合条件的情况下最终在结果集中形成最小树。

最小生成树(MTS)之Kruskal算法

而最终找到最小树路径

最小生成树(MTS)之Kruskal算法

来自B站UP主Compsyc计算之心

那么按着此场景的代码计算场景二是否合适？顺便说下其他场景是如何选择的

如图

最小生成树(MTS)之Kruskal算法

当指定C为起点时，如果是贪心算法的路径是

最小生成树(MTS)之Kruskal算法

路径：9+8+13+40 =70

显然这并不是最优解，其实TSP解决是最为合适的，但是要让其最后不返回起点才是最优解。

那么按着Kruskal算法先列举权重

最小生成树(MTS)之Kruskal算法

当前最短路径应该是

最小生成树(MTS)之Kruskal算法

10+13+8+10=41

如果用Dijkstra

列出其矩阵

最小生成树(MTS)之Kruskal算法

我们发现对角线全为0的即可不用计算，包含0的也可不计算

最小生成树(MTS)之Kruskal算法

如果按着两条相对斜边+对称点就是10+9+11+13+8（没有任何依据，单纯靠规律猜测）

计算的结果为

Connected to the target VM, address: '127.0.0.1:57912', transport: 'socket'指定起点为:A起点A到B点的最短路径是: A-10-B, 路径权值总和为: 10起点A到C点的最短路径是: A-10-B-9-C, 路径权值总和为: 19起点A到D点的最短路径是: A-10-B-8-D, 路径权值总和为: 18起点A到E点的最短路径是: A-10-B-9-C-10-E, 路径权值总和为: 29指定起点为:B起点B到A点的最短路径是: B-10-A, 路径权值总和为: 10起点B到C点的最短路径是: B-9-C, 路径权值总和为: 9起点B到D点的最短路径是: B-8-D, 路径权值总和为: 8起点B到E点的最短路径是: B-9-C-10-E, 路径权值总和为: 19指定起点为:C起点C到A点的最短路径是: C-9-B-10-A, 路径权值总和为: 19起点C到B点的最短路径是: C-9-B, 路径权值总和为: 9起点C到D点的最短路径是: C-11-D, 路径权值总和为: 11起点C到E点的最短路径是: C-10-E, 路径权值总和为: 10指定起点为:D起点D到A点的最短路径是: D-8-B-10-A, 路径权值总和为: 18起点D到B点的最短路径是: D-8-B, 路径权值总和为: 8起点D到C点的最短路径是: D-11-C, 路径权值总和为: 11起点D到E点的最短路径是: D-13-E, 路径权值总和为: 13指定起点为:E起点E到A点的最短路径是: E-10-C-9-B-10-A, 路径权值总和为: 29起点E到B点的最短路径是: E-10-C-9-B, 路径权值总和为: 19起点E到C点的最短路径是: E-10-C, 路径权值总和为: 10起点E到D点的最短路径是: E-13-D, 路径权值总和为: 13Disconnected from the target VM, address: '127.0.0.1:57912', transport: 'socket'

使用其他算法结果

Martix Graph: 0 10 20 0 40  10 0 9 8 0  20 9 0 11 10  0 8 11 0 13  40 0 10 13 0 DFS: A B C D E BFS: A B C E D PRIM(A)=19: A B C A A Kruskal=17: (A,D) (B,E) (B,D) (B,C) dijkstra(D):  shortest(D, A)=0 shortest(D, B)=8 shortest(D, C)=11 shortest(D, D)=0 shortest(D, E)=8

场景的第三种方法

找出客户与客户(端点与端点)之间的距离，按着从小到大排序后再重新计算

首先商户位置是确定的，第一轮找出距离商户最近的客户，然后下一轮将最近的客户当做商户去找剩下的客户中离'商户(第一个最近的客户)'的最近的客户，一次类推，但是每次都需要重新计算距离。

伪代码

 public void test(){ HashMap<String, String> map = new HashMap<>(); map.put("",""); String warehouse = String.format("%s,%s", "", "");
 backTrcking(map,warehouse); }
 private void backTrcking(HashMap<String, String> map, String warehouse) { BigDecimal temp = BigDecimal.ZERO; Stack<String> stack = new Stack<>(); for (String customerLocation : map.values()) { if(CollectionUtils.isNotEmpty(stack)){ warehouse = stack.pop(); } BigDecimal baseKilometreNum = IbsBMapUtils.getCarDistance(warehouse, customerLocation , "", "", "", "", "", "", 1, 1, 1, ""); if(baseKilometreNum.compareTo(temp) > 0){ temp = baseKilometreNum; } stack.add(customerLocation); }
 }

至此，我已私下尝试了多种算法去解决我现在的问题，但是由于对各大算法不是很精通，可能理解存在出入，并不是我想要的结果，时间原因后续会继续深入其他算法。

参考博文：https://blog.csdn.net/Real_Fool_/article/details/114141377https://blog.csdn.net/shui2104/article/details/107053966https://blog.csdn.net/weixin_44833195/article/details/106371435https://blog.csdn.net/coslay/article/details/47756917https://www.cnblogs.com/skywang12345/p/3711516.html