上传者: 42186579
|
上传时间: 2022-05-11 18:38:12
|
文件大小: 1.33MB
|
文件类型: PPT
1.最小生成树性质
用贪心算法设计策略可以设计出构造最小生成树的有效算法。
本节介绍构造最小生成树的Prim算法、Kruskal算法和Boruvka算法都可以看作是应用贪心算法设计策略的例子。尽管这几个算法做贪心选择的方式不同,它们都利用了下面的最小生成树性质:
设G=(V,E)是连通带权图,U是V的真子集。如果(u,v)E,且uU,vV-U,且在所有这样的边中,(u,v)的权c[u][v]最小,那么一定存在G的一棵最小生成树,它以(u,v)为其中一条边。这个性质有时也称为MST性质。