最小生成树

　在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。 　　

许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

下面给出Prim算法的基本思想，供参考：通过每次添加一个新节点加入集合，直到所有点加入停止的最小生成树的算法，每次连出该集合到其他所有点的最短边保证生成树的边权总和最小。

    （1）首先随便选一个点加入集合。

    （2）用该点的所有边去刷新到其他点的最短路。

    （3）找出最短路中最短的一条连接（且该点未被加入集合）。

    （4）用该点去刷新到其他点的最短路。

    （5）重复以上操作n-1次。

    （6）最小生成树的代价就是连接的所有边的权值之和。

[尚大教育软考学院提示]考试时如果是上午试题如果实在不会运用算法，就用选项中的答案去一个个验证，也许会更快一些。

假设如图4-3-1所示的无向图，要求最小生成树。

图4-3-1  要求最小生成树的图

使用Prim算法求解的步骤如图4-3-2所示。

图4-3-2    使用Prim算法求解的过程