软件下载：
链接：https://pan.baidu.com/s/1ypyIxnNngk-8XcqkcXSLQA 提取码：rpe6 复制这段内容后打开百度网盘手机App，操作更方便哦
2.3最小生成树问题
故事背景：有几个居民定居的村庄，需要在这些村庄之间建造道路，使得村民可以乘坐交通工具在村庄之间相互交流，问题是如何使花费最小而得到一条村村都互通的道路？
将其抽线为一个图的问题，可以假设一个解，包含若n个点的序列，形成一个没有回路的解。因为回路意味着道路的重复。因此应该有n-1条线段作为道路。寻找这n-1条线段组成的道路的最小值为最小生成树问题。有很多高效的方法来解决这个问题，本文采用的是Kruskal于1956年提出的【On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem】。
Kruskal的算法从最短的直线开始，然后依次添加剩余最短的不产生回路的直线，从而建立最小生成树。一旦找到了n-1条路线，则算法停止。
Kruskal算法：
设图G为一个n阶的连通加权图。图G中一个最小生成树T可以如下构造：选取图G中由最小权（权在这里指的是边长）的一条边e1，接着在图G-e1中选取一条具有最小权的边e2。当为T选取了k条边e1,e2,...,ek后，下一次选取ek+1的标准使权值尽量小且e1,e2,...ek+1没有形成圈。
同样使用前文所述的相切圆和护城河方法，使每个顶点p，半径的圆半径等速均匀增长，直到两圆相切，如图1(1)。
有出现相切圆的子集后，将两个相切圆的圆心点相连，相切圆子集以相切圆为轮廓等速向外延申护城河，如图1(2)-(4)。
Kruskal算法确保了我们确实找到了最小长度的生成树(它的正确构造很容易从最终的图片中验证)。因为任意更改一条线段的连接方式，必定会增加白色区域的长度，因此图3为最优解。
