一、最小生成树

• 连通所有顶点且总路径最小
• 修建连通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中包含了所有顶点；
  若第二步中遇到两条权值相同的最小权值边，任选一条即可，所以最小生成树可能不唯一，但权值之和相同。