最小生成树(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的话，按着我们的思路除非这三个客户在同一个方向，否则这种不考虑客户距离的送法是不合理的，那么真实的送货路线就变成了
这样实际的公里数是60km,而我们第一种场景的理论公里数是45km。
那么我们第二种暴力方法适合吗？又适用于哪种算法呢？
全排列的算法固然能考虑到每种方案，但是效率就过低了。
为什么不先介绍Bellman-Ford和Dijkstra算法？
首先Dijkstra用于计算一个节点到其他节点（不是所有节点到所有节点）的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想BSF)，直到扩展到终点为止，不适合当前场景。
而Bellman-Ford适用于计算单源最短路径，而不是走遍所有节点，也不适合。
Kruskal算法
求加权连通图的最小生成树。
1.所有权重从小到大排列
2.不能形成回环
示例
来自B站UP主Compsyc计算之心
先列举权重排列
如何防止回环？
每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路
感谢B站UP主Compsyc计算之心精心制作的算法解题视频，第一次刷到此视频就被其生动的文案所打动，视频风格和制作都很用心，推荐大家关注。
废话不多说让我们观赏下原视频
原创视频地址：
【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, 路径权值总和为: 13
Disconnected 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/114141377
https://blog.csdn.net/shui2104/article/details/107053966
https://blog.csdn.net/weixin_44833195/article/details/106371435
https://blog.csdn.net/coslay/article/details/47756917
https://www.cnblogs.com/skywang12345/p/3711516.html