6.4 图的应用

6.4.1 最小生成树（最小代价树）

概念： 一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边，即生成树是一个包含图的全部顶点的一个极小连通子图。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。

​ 对于一个带权连通无向图G=(V，E)，图G的生成树可能不唯一，对于不同的生成树，每棵树的权(即树中所有边上的权值之和)也可能不同。设R是由G的所有生成树构成的集合，若T为R中边的权值之和最小的那棵生成树，则称T为G的最小生成树(Minimum-Spanning-Tree，MST)。