数据结构论坛

注册

 

发新话题 回复该主题

算法笔记11最小生成树 [复制链接]

1#
帮助白癜风公益医院 http://ask.bdfyy999.com/

最小生成树的应用切分定理贪心算法加权无向图的数据结构Prim算法Kruskal算法最小生成树的应用

加权图是一种为每条边关联一个权值的图模型,这种图可以表示许多应用,比如在一副航空图中,边表示航线,权值就可以表示距离或费用;在一副电路图中,边表示导线,权值就可以表示导线的长度或成本。在这些情形中,最令人感兴趣的便是如何将成本最小化。最小生成树就是用于在加权无向图中解决这类问题的。最小生成树相关的算法在通信、电子、水利、网络、交通灯行业具有广泛的应用。

图的生成树是它的一颗含有其所有顶点的无环连通子图,一副加权无向图的最小生成树(Minimumspanningtree)是它的一颗权值(树中所有边的权值之和)最小的生成树。

切分定理

图的一种切分是将图的所有顶点分为两个非空且不重复的集合。横切边是一条连接两个属于不同集合顶点的边。通常通过指定一个顶点集并隐式地认为它的补集为另一个顶点集来指定一个切分。这样,一条横切边就是连接该集合的一个顶点和不在该集合中的另一个顶点的一条边。

切分定理

切分定理的内容为:在一副加权图中,给定任意的切分,它的横切边中的权重最小者必然属于图的最小生成树。切分定理是最小生成树算法的理论依据。要证明切分定理,需要知道树的两个重要性质:

用一条边连接树中的任意两个顶点都会产生一个新的环;从树中删去任意条边都将会得到两颗独立的树。接下来用反证法证明切分定理:令e为权值最小的横切边,T为图的最小生成树,假设T不包含e,那么将e加入T得到的图必然含有一条经过e的环,且这个环至少还有另一条横切边——设为f,f的的权重必然大于e(因为e的权重是最小的且图中所有边的权值都不相同)。那么删去f保留e就可以得到一颗权值更小的树,这与假设矛盾。贪心算法

切分定理是所有解决最小生成树问题算法的基础,这些算法都是一种贪心算法的特殊情况,贪心算法是一类在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是最好或最优的算法。解决最小生成树问题时,会使用切分定理找到最小生成树的一条边,不断重复直到找到最小生成树的所有边。这些算法之间的区别之处在于保存切分和判定权重最小的横切边的方式。

最小生成树的贪心算法:一副加权无向图中,在初始状态下所有边均为灰色,找到一种切分,它产生的横切边均不为黑色,将它权重最小的横切边标记为黑色,如此反复,直到标记了V-1条黑色边为止。

其中V为图中顶点的数量,那么要将这些顶点全部连接,至少需要V-1条边。根据切分定理,所有被标记为黑色的边都属于最小生成树,如果黑色边的数量小于V-1,那么必然还存在不会产生黑色边的切分,只要找够V-1条黑色边,最小生成树就完成了。

加权无向图的数据结构

加权无向图的数据结构没有沿用之前无向图的数据结构,而是重新定义了Edge和EdgeWeightedGraph类,分别用于表示带权重的边和加权无向图。

带权重的边Edge的实现

publicclassEdgeimplementsComparableEdge{privatefinalintv;privatefinalintw;privatefinaldoubleweight;publicEdge(intv,intw,doubleweight){this.v=v;this.w=w;this.weight=weight;}publicdoubleweight(){returnthis.weight;}publicinteither(){returnthis.v;}publicintother(intvertex){if(v==vertex)returnw;if(w==vertex)returnv;elsethrownewRuntimeException(Inconsistentedge);}publicint

分享 转发
TOP
发新话题 回复该主题