《数据结构域算法设计Ch4-3最小生成树--2》由会员分享，可在线阅读，更多相关《数据结构域算法设计Ch4-3最小生成树--2（27页珍藏版）》请在金锄头文库上搜索。
1、Ch4最小生成树 加权无向图高文宇 1最小生成树 Minimum Spanning Tree 图的生成树是包含图的 所有顶点的无环连通子 图。一个加权无向图的 最小生成树（MST）是 该图的一棵权值最小的 生成树。2切分定理 切分定理：在一个加权图中，给定任意的 切分，它的横切边中权值最小的边一定属 于该图的最小生成树。 最小生成树的贪心算法：找出最小权值边 ，它一定属于最小生成树，以此类推。3最小生成树的贪心算法 Proposition K. ( Greedy MST algorithm) The following method colors black all edges in the
2、the MST of any connected edgeweighted graph with V vertices: starting with all edges colored gray, find a cut with no black edges, color its minimum -weight edge black, and continue until V1 edges have been colored black.4加权无向图-Edge API EdgeComparable接口 定义使用了泛型5EdgeWeightedGraph API EdgeWeightedGrap
3、hInterable接 口定义使用 了泛型6EdgeWeightedGraph EdgeWeightedGraph7Edge类 Edge类8EdgeWG类 EdgeWeightedGraph9MST API MST计算得到的最小生成树采用一组边 来表示。即在edges()方法中返回。10Prim算法 Prims algorithm：Prim算法的每一步都会 为一棵生长中的树添加一条边。一开始这 棵树只有一个顶点，然后给它添加V-1条边 ，每次总是将下一条连接树中顶点与不在 树中的顶点且权值最小的边加入树中。11Prim算法 Prim12Prim算法的数据结构 顶点：使用一个布尔数组marked
4、，若顶点 v已在MST中，那么markedv=true。 边：用一个队列mst来保存属于MST的边。 或者一个由顶点索引的Edge对象数组 edgeTo，其中edgeTov为将v连接到树中 的Edge对象。 横切边：使用一个优先队列MinPQ 来根据权重比较所有的边，以便随时可以 回答“哪条边权值最小”这个问题。13Prim算法的Lazy实现 每当向树中添加一条边之后，同时也向树中添加 了一个顶点。要维护一个包含所有横切边的集合 ，就要将连接这个顶点和其它所有不在树中的顶 点的边加入优先队列。 但有一点，连接新加入树中的顶点与其它已经在 树中的顶点的所有边都失效了（这种边的两个端 点都在树中）
5、。 Prim算法的即时实现可以将这种失效边即时地从 优先队列中删除。 而Prim算法的延时实现则是先将这些失效边留在 优先队列中，等到要删除它们的时候再检查边的 有效性。14Prim算 法的 Lazy实 现 LazyPrimMST15Prim算法Lazy实现的复杂度 Proposition M. The lazy version of Prims algorithm uses space proportional to E and time proportional to E log E (in the worst case) to compute the MST of a connected
6、 edge-weighted graph with E edges and V vertices.16Prim算法的即时实现 PrimMST 要改进LazyPrimMST，可以尝试从优先队列中删除失效 边，这样优先队列中就只含有树顶点和非树顶点之间的横 切边。但事实上还可以删除更多的边。 当我们将顶点v加入到树中时，我们不需要在PQ中保存所 有非树顶点到v的边，而只需保存权重最小的那条。 换句话说，我们只需要在PQ中保存每个非树顶点w的一条 边：将它与树中顶点相连的那条权值最小的边。 若顶点v不在树中但至少有一条从v发出的边与树相连，那 么edgeTov是将v和树连接的最短边，distTov为
7、这条变 的权值。17PrimMST Prim18Prim算法即时实现的复杂度 Proposition N. The eager version of P rims algorithm uses extra space proportional to V and time proportional to E log V (in the worst case) to compute the MST of a connected edgeweighted graph with E edges and V vertices. Proof: The number of edges on the prio
8、rity queue is at most V, and there are three vertex-indexed arrays, which implies the space bound. The algorithm uses V insert operations, V delete the minimum operations, and (in the worst case) E change priority operations. These counts, coupled with the fact that our heap-based implementation of
9、the index priority queue implements all these operations in time proportional to log V (see page 321), imply the time bound.19Kruskal算法 按照边的权重顺序（从小到大）来处理， 将边逐条加入到最小生成树中，加入的边 不能与已经加入的边构成环，直到树中包 含V-1条边为止。20Kruskal算法 Kruskal算法21Kruskal Kruskal22Kruskal算法复杂度Proposition N (continued). Kruskals algorithm
10、uses space proportional to E and time proportional to E log E (in the worst case) to compute the MST of an edgeweighted connected graph with E edges and V vertices. Proof: The implementation uses the priority-queue constructor that initializes the priority queue with all the edges, at a cost of at m
11、ost E compares (see Section 2.4). After the priority queue is built, the argument is the same as for Prims algorithm. The number of edges on the priority queue is at most E, which gives the space bound, and the cost per operation is at most 2 lg E compares, which gives the time bound. Kruskals algor
12、ithm also performs up to E find() and V union() operations, but that cost does not contribute to the E log E order of growth of the total running time (see Section 1.5).23MST算法的性能比较20世纪70年代优先队列发明后，被应用于寻找稀疏图的最小生成树。 1984年，M.L.Fredman和R.E.Tarjan发明了斐波那契堆，将Prim算法 所需允许时间在理论上改进到E+VlogV。24练习 Prim算法和Kruskal算
13、法能处理有向图吗？ 4.3.3 Show that if a graphs edges all have distinct weights, the MST is unique. 4.3.12 Suppose that a graph has distinct edge weights. Does its shortest edge have to belong to the MST? Can its longest edge belong to the MST? Does a min-weight edge on every cycle have to belong to the MST?
14、Prove your answer to each question or give a counterexample.25练习 4.3.14 Given an MST for an edge-weighted graph G, suppose that an edge in G that does not disconnect G is deleted. Describe how to find an MST of the new graph in time proportional to E. 4.3.15 Given an MST for an edge-weighted graph G
15、 and a new edge e, describe how to find an MST of the new graph in time proportional to V. 4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to E log E . Note : This question assumes that edge weights are not necessarily distinct (otherwise all edges in the MST are critical).26再见再见27
