Kruskal算法的应用及其Matlab实现心得（转载）

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

Kruskal算法常用于实际生活中最短路径规划问题等，现有问题如下：

      在村村通自来水工程实施过程中，从保证供水质量以及设备维护方便角度出发，某地区需要建设一个中心供水站，12个一级供水站和168个二级供水站，各级供水站的位置坐标如表1所示，其中类型A表示中心供水站，类型V代表一级供水站，类型P为二级供水站。

水站位置

      现在要将中心供水站A处的自来水通过管道输送到一级供水站和二级供水站。按照设计要求，从中心站A铺设到一级供水站的管道为I型管道，从一级供水站出发铺设到二级供水站的管道为II型管道。已提供水站位置的坐标，中心水站只能连接一级、一级只能连接二级水站，要求给出最短路径。

一、将所有连接方式全部存储为181*181矩阵G，内容为每两点之间的距离。

G矩阵

二、对有用的方案进行选择之后。存储为【距离、位置一序号、位置二序号】形式的三元矩阵

存储

三、将之按照距离从小到大排列，由小到大依次连接，直到遇到封闭环，继续取再之上的值继续连接，直到覆盖所有点。

判别环函数

主函数

四、结果可视化

结果

可视化程序

【如有侵权，可联系我删除），小伙伴有兴趣的了解更多关于matlab的使用，可以关注一下我的公众号程式解说】

五、补充

有时也会在进一步要求二级管道最短，提出升级水站的问题，只需要进一步遍历结果即可。

很多类似问题也可以拿他进行求解，实际生活中，也可以将实际的地形等因素加以权重考虑进去，近似为本题中的距离。

作者：当代网瘾少年

（转载自）https://www.bilibili.com/read/cv15068133?from=search&spm_id_from=333.337.0.0出处：bilibili

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Kruskal算法 matlab实现 Kruskal MATLAB matla