作业1最小生成树的生成算法

1.1算法应用背景

在实际生活中，图的最小花费生成树问题有着广泛的应用。例如，用图的顶点代表城市，顶点与顶点之间的边代表城市之间的道路或通信线路，用边的权代表道路的长度或通信线路的费用，则最小花费生成树问题，就表示为城市之间最短的道路或费用最小的通信线路问题。其中普里姆算法是使用贪婪法策略设计的典型算法。

1.2算法原理

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。

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

1.3算法描述

1)最小生成树之普里姆算法描述：

令G=(V,E,W)，为简单期间，令顶点集为V={0,1,2…，n-1}。假定与顶点i，j相关联的边为ei，j, ei，j的权用c[i][j]表示，T是最小花费生成树的边集。这个算法维护两个顶点集合S和N，开始时：令T=Ф,S={0},N=V-S。然后，进行贪婪选择，选取i∈S，j∈N，并且c[i][j]最小的i和j；并使S=S∪S{j},N=N-{j},T=T∪{ei，j}.重复上述步骤，直到N为空，或找到n-1条边为止。此时，T中的边集，就是所要求取的G中的最小花费生成树。由此，可描述普里姆算法的步骤如下：

（1）T=Ф，S={0},N=V-S。

（2）如果N为空，算法结束；否则，转步骤（3）。 （3）寻找使i∈S，j∈N，并且c[i][j]最小的i和j。 （4）S=S∪S{j},N=N-{j},T=T∪{ei，j}；转步骤（2）。 2)用贪心策略解普里姆算法的正确性证明

普里姆算法所产生的最小代价生成树的边集是 T，无向赋权图G 的最小代价生成树的