最小生成树之Kruskal算法
注意：内容学习来自：b站CleverFrank数模算法精讲
导航
前言实际问题引入Kruskal算法整体代码展示尾声
前言
博主今天给大家带来的是最小生成树中两个经典算法Kruskal算法和Prim算法中的Kruskal算法。
今天的内容对大家图论和图的相关基础知识有一定考察。大家在食用本篇之前要稍微了解一下Matlab生成图的方式和图相关数据结构的一些操作。
那么这里博主先安利一下一些干货满满的专栏啦！
数据结构专栏：数据结构 这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
算法专栏：算法 这里可以说是博主的刷题历程，里面总结了一些经典的力扣上的题目，和算法实现的总结，对考试和竞赛都是很有帮助的！
力扣刷题专栏：Leetcode 想要冲击ACM、蓝桥杯或者大学生程序设计竞赛的伙伴，这里面都是博主的刷题记录，希望对你们有帮助！
C的深度解剖专栏：C语言的深度解剖 想要深度学习C语言里面所蕴含的各种智慧，各种功能的底层实现的初学者们，相信这个专栏对你们会有帮助的！
实际问题引入
其实这道题的答案，其实就是找到这个图的最小生成树。
Kruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。
s=[1,1,1,1,2,2,3,3,4,4,5,5,6];t=[2,3,4,5,3,6,5,7,5,6,6,7,7];w=[35,24,10,25,25,20,15,11,12,30,15,25,18];names={'1','2','3','4','5','6','7'};G=graph(s,t,w,names);p=plot(G,"EdgeLabel",G.Edges.Weight);% 求解最小生成树T=minspantree(G,"Method","sparse");% sparse代表的是Kruskal算法% dense代表的是Prim算法% sparse:Kruskal算法% 算法按权重对所有的边排序，然后将不构成循环的边添加到树中p=plot(G,"EdgeLabel",G.Edges.Weight);highlight(p,T,"NodeColor","red","EdgeColor","red"); % 将最小生成树的边设置为红色!生成的图：
生成的最小生成树：
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声
看到这里，相信我们已经学会Kruskal算法寻找最小生成树的过程了，当然，这离数学建模的要求，离我们的目标还非常遥远，博主在不断学习的过程中，也希望可以通过分享学习日记的方式带动大家！如果你感觉这篇文章对你有帮助的话，不要忘了点赞！关注！收藏噢！