|
8.5最小生成树
最小生成村树有很多种解决方案，可以分为几类：
1.创建并扩展一些树，使它们合并成更大的树(Boruvka)
2.创建一个树的集构成一棵生成树(Kruskal)
3.创建并扩展一棵树，为它添加新的树枝(Prim)
4.创建并扩展一棵树，为它添加新的树枝，也可能从中删除一些树枝(Dijkstra)
8.5.1 Boruvka算法：
最早的查找最小生成树的算法可能是1926年Otakaar.Boruvka提出的。在这个方法中，我们从有|V|个顶点的树的某个顶点开始，然后对每个顶点v查找所有从v向外的边中权最小的edge(vu)并创建一个包括这些边的最小的树。然后，查找能够将这些树连接成一个大树的权最小的边。创建好一棵树之后，程序结束。
BoruvkaAlgorithm(带权连通无向图 graph)
令每一个顶点都成为一棵单顶点树的根;
while 单顶点树的数量大于1
for 每棵树t
e = 权值最小的边(vu)，其中v在树t中而u不属于t;
将树t和包含顶点u的树连接成一棵树，如果它尚未创建的话;
说明：
在while循环珠每次重复中，每个现存的r树和一条边相连，得到至少一棵树。最坏情况下，产生r/2棵树；最好情况下，产生一棵树。后来的重复中，有r/4棵树等等。最坏情况下，需要lg|V|次重复，|V|是单顶点树的初始值。Boruvka算法非常适合并行处理，因为对于每一棵树，必须独立地找到最小边。
8.5.2 Kruskal算法
先把所有的边根据权排序，然后检测这个排序序列中的每一条边，看一下在构造时，它能否考虑成为树的一部分。如果加入它不产生环路就将它添加到树中。
KruskalAlgorithm(带权连通无向图 graph)
tree = null;
edges = 按照权值大小排序的graph的全部边;
for (i = 1; i <= |E| and |tree| < |V| - 1; i++)
if edges中的边edges[i]和tree中的边不产生环路
将edges[i]加进tree;
说明：
这个算法的复杂度是由所采用的排序复杂度确定的，对一个有效的排序的复杂度，对一个有效的排序的复杂度是O(|E|lg|E|)。它也依赖于环路检测方法的复杂度。如果使用union()实现Kruskal算法，那么for循环变成
for (i = 1; i <= |E| and |tree| < |V| - 1; i++)
union(edge[i] = edge(vu));
尽管union()可以被调用至多|E|次，在检测到一个环路(第一次)之后它就退出并且执行一个联合，复杂度是O(|V|)，只将|V|-1条边加入到tree中。因些KruskalAlgorithm的for循环的复杂度是O(|E| + (|V| - 1)|V|)，也就是O(|V|^2)。所以KruskalAlgorithm的复杂度取决于一个排序算法的复杂度O(|E|lg|E|)。
8.5.3 Jarnik.Prim算法
在这个方法中，开始时所有的边都是排序的，但是准备加入生成树的边不仅不会在树中产生环路，而且也和树中已经有的一个顶点关联。
JarnikPrimAlgorithm(带权连通无向图 graph)
tree = null;
edges = 按权值大小排序的graph的全部边
for i = 1 到|V| - 1
for j = 1 到 |edges|
if edges 中的边edges[j]和tree中的边不会产生回路并且和tree中的一个顶点关联
将edges[j]添加进tree;
break;
8.5.4 Dijkstra算法
JarnikPrimAlgorithm(带权连通无向图 graph)
tree = null;
edges = 未排序的graph全部边;
for j = 1 到 |edges|
将edges[j]添加进tree;
if 在tree中有环路
从这个环路中删除权值最大的一条边;
|
