一、最小生成树
- 连通所有顶点且总路径最小
- 修建连通7个城市的铁路网，可修建的路线和对应造价如图所示，如何修建使总费用最少？
- 问题分析：
连通7个城市：生成的图中，从任意顶点起步，沿着边一定可以到达所有的其他顶点，这种图叫连通图。
可修建的路线和对应造价：图的边，及其权值。
总费用最少：权值之和最少。
和最短路径的区别：最短路径是针对某一顶点作为起点而言的，最小生成树是所有顶点连通且总路径最小。
二、最小生成树的求解
- Matlab中的minspantree( )函数进行求解
s = [1,1,2,2,3,3,4,4,4,5];
t = [2,3,4,5,4,7,5,6,7,6];
weights = [50,60,65,40,52,45,50,30,42,70];
% 生成无向图，其中s和t对应元素代表边，weights是权值
G = graph(s,t,weights);
% 求出最小生成树，得到的T包含最小生成树的节点和对应边的权值
T = minspantree(G);
% p = plot(G)可以把图片展现出来
p = plot(G)
% 突出显示绘制的图中的节点和边
highlight(p,T,'EdgeColor','red','LineWidth',3)
- Kruskal算法（适合点多边少的图）
把图G中的所有边全部去掉，得到所有单独的顶点V构成图T = （V，｛｝），其中V是顶点集合；
从G中取出当前权值最小的边，如果该边加入T的边集合后T不形成回路，则加入T；否则舍弃；
重复第二步，直到T中有n-1条边（n是顶点数）；
若第二步中遇到两条权值相同的最小权值边，任选一条即可，所以最小生成树可能不唯一，但权值之和相同。 - Prim算法（适合边多点少的图）
设置一个图U，将原图G中任意一顶点取出加入U中；
在所有的u∈U，v∈（G－U）的边（g，u）中找到一条权值最小的边，并入图U中；
重复步骤二，直到U中包含了所有顶点；
若第二步中遇到两条权值相同的最小权值边，任选一条即可，所以最小生成树可能不唯一，但权值之和相同。
文章来源地址https://www.toymoban.com/news/detail-451873.html
文章来源：https://www.toymoban.com/news/detail-451873.html
到了这里，关于最小生成树matlab求解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
