最小生成树(MTS)之Kruskal算法
【摘要】 Kruskal 算法是最小生成树（minimum spanning tree ）的经典算法之一。这是个很努力的算法，不放弃任何一个可能的机会，尝试了每一条边。成环不会阻挠它前进的脚步，不紧不慢不卑不亢，最终带给我们人类一个满意的结果。虽然不是MST中最聪明的，但却是很可爱的B站UP主Compsyc计算之心 常见的数据结构中树的应用较多一些，在树的节点关系中称之为父子关系，而在一些特定场...
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的话，按着我们的思路除非这三个客户在同一个方向，否则这种不考虑客户距离的送法是不合理的，那么真实的送货路线就变成了
这样实际的公里数是60km,而我们第一种场景的理论公里数是45km。
那么我们第二种暴力方法适合吗？又适用于哪种算法呢？
全排列的算法固然能考虑到每种方案，但是效率就过低了。
为什么不先介绍Bellman-Ford和Dijkstra算法？
首先Dijkstra用于计算一个节点到其他节点（不是所有节点到所有节点）的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想BSF)，直到扩展到终点为止，不适合当前场景。
而Bellman-Ford适用于计算单源最短路径，而不是走遍所有节点，也不适合。
Kruskal算法
求加权连通图的最小生成树。
1.所有权重从小到大排列
2.不能形成回环
示例
先列举权重排列
如何防止回环？
每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路
感谢B站UP主Compsyc计算之心精心制作的算法解题视频，第一次刷到此视频就被其生动的文案所打动，视频风格和制作都很用心，推荐大家关注。
废话不多说让我们观赏下原视频
，时长02:10
原创视频地址：
【Kruskal算法之通用版 | 最小生成树MST | 无代码可视化纯享版-哔哩哔哩】 https://b23.tv/o35bzQ我也自己参考做了几张图
每次开始筛选最小边路径，然后在符合条件的情况下最终在结果集中形成最小树。
而最终找到最小树路径
来自B站UP主Compsyc计算之心
那么按着此场景的代码计算场景二是否合适？顺便说下其他场景是如何选择的
如图
当指定C为起点时，如果是贪心算法的路径是
路径：9+8+13+40 =70
显然这并不是最优解，其实TSP解决是最为合适的，但是要让其最后不返回起点才是最优解。
那么按着Kruskal算法先列举权重
当前最短路径应该是
10+13+8+10=41
如果用Dijkstra
列出其矩阵
我们发现对角线全为0的即可不用计算，包含0的也可不计算
如果按着两条相对斜边+对称点就是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
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论（0）