文档介绍：算法分析与设计
—贪心算法求解最小生成树问题
学号:
姓名:
代课老师:
最小生成树
问题描述:考虑无向图G=(V,E),假定该图代表不同城市间的通信网络情况,图的顶点表示城市,边(v,w)的权值c[v][w]表示建立城市v和w之间的通信线路所需的费用,这样得到一个无向连通带权图。在实际问题中,人们往往希望在该结构上选择一组通信线路,它们连接所有的城市并且是最经济的方案。
问题分析:该问题相当于求解连通带权图的具有最小权值的生成树,我们称之为最小生成树问题。
相关概念
最小生成树:设G =(V,E)是无向连通带权图,即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树。
最小生成树的性质:设G=(V,E)是连通带权图,U是V的真子集。如果(u,v)E,且uU,vV-U,且在所有这样的边中,(u,v)的权c[u][v]最小,那么一定存在G的一棵最小生成树,它以(u,v)为其中一条边。这个性质有时也称为MST性质。
贪心算法的基本要素
贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本要素是贪心选择性质和最优子结构性质。
证明最小生成树问题满足最优子结构性质:
假设G的任何一棵最小生成树都不含边(u,v)。将边(u,v)添加到G的一棵最小生成树T上,将产生含有边(u,v)的圈,并且在这个圈上有一条不同于(u,v)的边(u',v'),使得u'U,v'V-U ,如图所示:
将边(u',v')删去,得到G的另一棵生成树T'。由于c[u][v]≤c[u'][v'],所以T'的耗费≤T的耗费。意识T'是一棵含有边(u,v)的最小生成树,这与假设矛盾。
U
V-U
u
u'
v
v'
Prime算法
基本思想:设G=(V,E)是连通带权图,V={1,2,…,n}。首先设S={1},然后,只要S是V的真子集,就做如下的贪心选择:选取满足条件iS,jV-S,且c[i][j]最小的边,并将顶点j添加到S中。这一过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
基础:G的最小生成树的边数是顶点数-1。
Prime算法选边过程:
1
2
6
5
4
3
6
1
5
5
3
5
2
6
4
6
1
2
6
5
4
3
1
1
2
6
5
4
3
1
4
1
2
6
5
4
3
4
1
2
1
2
6
5
4
3
4
1
2
5
4
1
3
5
2
1
2
6
5
4
3
算法相关说明
c[i][j]:边(i,j)的权
S[]:标记已经加入到最小生成树T的顶点
closest[j]:对于每一个jV-S是j在S中的邻接顶点,它与j在S
中的其他邻接顶点k相比较有:c[j][closest[j]]≤c[j][k]
lowcost[j]:即c[j][closest[j]]
Prime算法:先找出V-S中使lowcost值最小的顶点j,然后根据书中closest选取边(j,closest[j]),最后将j添加到S中, 并对closest和lowcost做必要的修改。
时间复杂度: ,n是顶点个数
public class Prim {
public static void prim(int num, float[][] weight) { //num为顶点数,weight为权
float[] lowcost = new float[num + 1]; //到新集合的最小权
int[] closest = new int[num + 1]; //代表与s集合相连的最小权边的点
boolean[] s = new boolean[num + 1]; //s[i] == true代表i点在s集合中
s[1] = true; //将第一个点放入s集合
for(int i = 2; i <= num; i++) { //初始化辅助数组
lowcost[i] = weight[1][i];closest[i] = 1;s[i] = false;}
for(int i = 1; i < num; i++) {
("第" +