Ch最小生成树..ppt

Ch4最小生成树加权无向图 高文宇 gwyy@163.com 最小生成树 Minimum Spanning Tree 图的生成树是包含图的所有顶点的无环连通子图。一个加权无向图的最小生成树（MST）是该图的一棵权值最小的生成树。 切分定理 切分定理：在一个加权图中，给定任意的切分，它的横切边中权值最小的边一定属于该图的最小生成树。 最小生成树的贪心算法：找出最小权值边，它一定属于最小生成树，以此类推。 最小生成树的贪心算法 Proposition K. ( Greedy MST algorithm) The following method colors black all edges in the 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. 加权无向图--Edge API Edge EdgeWeightedGraph API EdgeWeightedGraph EdgeWeightedGraph EdgeWeightedGraph Edge类 Edge类 EdgeWG类 EdgeWeightedGraph MST API MST—计算得到的最小生成树采用一组边来表示。即在edges()方法中返回。 Prim算法 Prim’s algorithm：Prim算法的每一步都会为一棵生长中的树添加一条边。一开始这棵树只有一个顶点，然后给它添加V-1条边，每次总是将下一条连接树中顶点与不在树中的顶点且权值最小的边加入树中。 Prim算法 Prim Prim算法的数据结构 顶点：使用一个布尔数组marked[]，若顶点v已在MST中，那么marked[v]=true。 边：用一个队列mst来保存属于MST的边。或者一个由顶点索引的Edge对象数组edgeTo[]，其中edgeTo[v]为将v连接到树中的Edge对象。 横切边：使用一个优先队列MinPQEdge来根据权重比较所有的边，以便随时可以回答“哪条边权值最小”这个问题。 Prim算法的Lazy实现 每当向树中添加一条边之后，同时也向树中添加了一个顶点。要维护一个包含所有横切边的集合，就要将连接这个顶点和其它所有不在树中的顶点的边加入优先队列。 但有一点，连接新加入树中的顶点与其它已经在树中的顶点的所有边都失效了（这种边的两个端点都在树中）。 Prim算法的即时实现可以将这种失效边即时地从优先队列中删除。 而Prim算法的延时实现则是先将这些失效边留在优先队列中，等到要删除它们的时候再检查边的有效性。 Prim算法的Lazy实现 LazyPrimMST Prim算法Lazy实现的复杂度 Proposition M. The lazy version of Prim’s algorithm uses space proportional to E and time proportional to E log E (in the worst case) to compute the MST of a connected edge-weighted graph with E edges and V vertices. Prim算法的即时实现 PrimMST 要改进LazyPrimMST，可以尝试从优先队列中删除失效边，这样优先队列中就只含有树顶点和非树顶点之间的横切边。但事实上还可以删除更多的边。 当我们将顶点v加入到树中时，我们不需要在PQ中保存所有非树顶点到v的边，而只需保存权重最小的那条。 换句话说，我们只需要在PQ中保存每个非树顶点w的一条边：将它与树中顶点相连的那条权值最小的边。 若顶点v不在树中但至少有一条从v发出的边与树相连，那么edgeTo[v]是将v和树连接的最短边，distTo[v]为这条变的权值。 PrimMST Prim Prim算法即时实现的复杂度 Proposition N. The eager version of P rim’s 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