第九讲   最小生成树

            （教材：第九章   最小生成树）

1 2 3(本页) 4 5 6

算法二 (普赖姆，Prim)   

    这是一种迭代算法，每进行一次迭代将产生组成网络 最小生成树 的一条边。其作法基于下面的事实：如果我们已经知道 中的一些边，它们的端点组成点集 ， 是 的顶点集 的一个子集。以 记一个端点在 中、另一端点在 中的所有边组成的集合。因为最小生成树 是 的连通生成子图，必有边连接点集 和点集 内的点，这样， 中权最小的一条边也应该是 的最小生成树 中的一条边。

    设 为边 的权。如果 与 之间无边相连，则取 。为叙述方便，我们以顶点的下标来表示 中的顶点。

普赖姆迭代过程

 〔例1〕求上面图 9.1（教材 p110页图）所示的网络 最小生成树 。

   我们用图显示普赖姆方法的各步骤。图中标出了该步骤应该考虑的各边的权，不标出不需考虑的边的权。在该步骤中取的点和边画成蓝色，该步骤前已经取的点和边画成红色。

     (1) 算法开始时，。因为 ，所以取 。

     (2) 把 不在 中的一个端点 加入到 中，于是，中权最小的边为 和 ，任取一条边，例如把 加到 中，则 。

     (3) 把 不在 中的另一端点 加进 中，此时 其中权最小的边为 ，取 。

     (4) 把 不在 中的一端点 加入 中，则 ，其中权最小的边为 ，从而取 。

     (5) 把 不在 中的一个端点 加进 中，此时 ，，故算法终止。

     此时以为顶点集、 为边集的树 即为 的最小生成树。

1 2 3(本页) 4 5 6