设为 N=(V,E,C)连通网，TE是N的最小支撑树的边的集合。

① 算法开始时， U= {u o }(u o ∈ V), TE= ○ ；

② 找到满足

weight(u,v)=min{weight(u 1 ,v 1 )| u 1 ∈ U, v 1 ∈ V-U }, 的边，把它并入集合

TE中，v同时并入U。

③ 反复执行② ,直至 V=U 时终止算法。

普里姆算法执行过程示例

由上述图解算法的过程知，构造的最小生成树不一定唯一，但最小生成树的权值之和一定是相同的 。

最小支撑树生成树

由图遍历的过程中经过的边加上图的所有顶点所构成的子图。

最小支撑树生成树的特点

（1）n个顶点的连通子图的生成树是一个极小连通子图，它包含图中所有顶点和n-1条边（但有n-1条边的图不一定是生成树）。

（2）生成树中任意两个顶点间的路径是唯一的。

最小支撑树树的权

生成树T各边的权值总和称为该树的权。

最小支撑树最小生成树

将权最小的生成树称为图的最小生成树。

Krusal算法和Prim算法是两个构造最小生成树的著名算法。

一个网络图可以有多个生成树．记N的所有生成树的集合为：

设

则称 T * 为网络N的一棵最小树树形图，简称最小树。

求最小树的两种方法，是避圈法与破圈法 。

最小树形图问题避圈法

从网络图中任意节点开始寻找与该节点关联的权数最小的边，使之与已选边不构成为圈，直到选够n-1条边为止。

最小树形图问题破圈法

① 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；

② 去掉该圈中权数最大的边；

反复重复 ① ② 两步，直到最小树。

最小树形图问题Kruskal 算法

将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集 T，只要不和前面加入的边构成回路，直到 T 中有 n-1 条边，则 T 是最小生成树。

树形图的概念

无圈且连通的无向图称为树。树一般记为T。作为树定义还可以有以下几种表述：

(1) T 连通且无圈或回路；

(2) T 无圈且有n－1条边（如果有n个结点）；

(3) T 连通有n－1条边；

(4) T 无回路，但不相邻的两个结点之间联以一边，恰得一个圈；

(5) T 连通，但去掉T 的任意一条边，T 就不连通了；（亦即在点集合相同的图中，树是含边数最少的

连通图。）

(6) T 的任意两个结点之间恰有一条初等链。