定义2。2。2 设图是的生成（支撑）子图，如果是一个树，则称和的一个生成树（支撑树）。

定义2。2。3 给图，对中的每以条边，相应地有一个数，则称这样的图为赋权图，称为边上的权。

本章介绍的两种算法都是对赋权图求其最小生成树，那么什么是最小生成树呢？

定义2。2。4 给图是的一个生成树，中的所有边的权之和称为生成树的权，记为，并且。的最小值记为，最小生成树记为。

由于第三章给出的基于最小度约束下的最小生成树算法需要用到Prim算法以及Kruskal算法，首先我们来介绍普利姆（Prim）算法，用普利姆算法对加权无向图求最小生成树的过程是：

（1）初始化是一个空集，首先从图中任取一个节点加入，，此时图中的顶点就被分成两个部分，一个是，另一个则包括所有不属于的顶点。确定当前的外部边集，外部边集包括从属于的任意顶点到所有不属于的顶点的最短边。外部边集连接了和所有可连接的外部顶点。来;自]优Y尔E论L文W网www.youerw.com +QQ752018766-

（2）取出外部边集中的最短边，把这条边和非顶点加入，此时，中的顶点数目增加。

（3）更新外部边集。

（4）重复步骤（2）和（3），直到包括中所有顶点。我们就得到了图的最小生成树。

构造最小生成树的准则是使用该图中的边来构造生成树。必须用且仅用条边来连接该图的个顶点；并且不能使用产生回路的边。这两条边实际上是一致的，因为如果采用了能够产生回路的边，那么个顶点，条边构成的子图必定不连通，因此这条边也不能构成生成树；如果条边能使这个顶点连通，那么其中也一定不存在回路。

我们来考虑这样一个实际的问题，要建设一个全国性通信网络，其主干网要将一些选定的大城市连接起来，如图2-1所示，再通过这些大城市向其周围地区辐射，从而实现对全国的覆盖。在这些大城市两两之间都可以架设通信线路，但代价是不同的。如果为通信主干网的建设设计一个最小的方案，我们就可以用图来描述这个问题。每个城市都是图中的一个顶点，连接城市的线路是边，边上是权值即为建设成本。不同的通信线路建设方案实际上就是不同的生成树，而图的最小生成树就对应去其中建设成本最小的方案。