《算法课件Lecture5章节》由会员分享，可在线阅读，更多相关《算法课件Lecture5章节（29页珍藏版）》请在金锄头文库上搜索。
1、2019/6/21 2004 SDU,Lecture 5 Minimum Spanning Tree,The Minimum Spanning Tree Problem A Generic Algorithm Kruskals Algorithm Prims Algorithm, 2004 SDU 2,An Application,In the design of networking Given n computers, we want to connect them so that each pair of them can communicate with each other. Eve
2、ry foot of cable costs us $1 We want the cheapest possible network.,In the design of electronic circuitry Given n pins that should be electrically equivalent by wiring them together To interconnect a set of n pins, n-1 wires can be used, each connecting two pins We want the least possible length of
3、wire to save cost, 2004 SDU 3,Minimum Spanning Tree- The Definition,Given a connected undirected graph G = (V, E) and an assignment of weights w(e) to the edges of G, a minimum spanning tree T of G is a spanning tree with minimum total edge weight,Note: (1). A spanning tree of a graph is an acyclic
4、subgraph that connects all vertices. (2). A connected undirected graph may have many different spanning trees (3). The minimum spanning tree may not be unique, 2004 SDU 4,Minimum Spanning Tree Problem,The Problem: Input: A connected, weighted, undirected graph G = (V, E; W). Output: A minimum spanni
5、ng tree T for G., 2004 SDU 5,Idea of the Generic Algorithm,It grows the minimum spanning tree one edge at a time. The algorithm manages a set of edges A, maintaining the following loop invariant: Prior to each iteration, A is a subset of some minimum spanning tree. An edge (u, v) is a safe edge for
6、A if A(u, v) is also a subset of of a minimum spanning tree, that is, (u, v) can be safely added to A without violating the invariant Kruskals and Prims algorithms are implementations of the generic algorithm on how to maintain A and find the safe edge (u, v) for A., 2004 SDU 6,A Generic Algorithm,
7、2004 SDU 7,A cut (X, Y) of a graph G = (V, E) is a partition of the vertex set V into two sets X and Y = V X. An edge (u, v) E is said to cross the cut (X, Y) if u X and v Y. A cut (X, Y) respects a set A of edges if no edge in A crosses the cut. An edge is a light edge crossing a cut if its weight
8、is the minimum of any edge crossing the cut.,Related Notions,Set of red vertices X and set of green vertices Y form a cut (X, Y) of the graph. Blue edges cross the cut (X, Y) (X, Y) respects a set A of edges consisting only red or green edges., 2004 SDU 8,Determine Safe Edges for A,Theorem 23.1 Let
9、G = (V, E) be a connected, undirected graph with real-valued weight function w defined on E. Let A be a subset of E that is included in some minimum spanning tree for G, let (X, Y) be any cut of G that respects A, and let (u, v) be a light edge crossing (X, Y). Then, edge (u, v) is safe for A., 2004
10、 SDU 9,The Proof of Theorem 23.1,Proof: Let T be a MST including A, and assume that T does not contain the light edge (u, v). We shall construct another MST T that includes A(u, v), showing that (u, v) is a safe edge for A. The edge (u, v) forms a cycle with the edges on the path from u to v in T. S
11、ince u and v are on opposite sides of the cut (X,Y), there is at least one edge in T on the path p that also crosses the cut. Let (x, y) be any such edge. The edge (x, y) is not in A since the cut respects A. Since (x, y) is on the unique path from u to v in T, removing (x, y) breaks T into two comp
12、onents. Adding (u, v) reconnects them to form a new spanning tree T = T-(x, y) (u, v)., 2004 SDU 10,A Corollary,Corollary 23.2 Let G = (V, E) be a connected, undirected graph with real-valued weight function w defined on E. Let A be a subset of E that is included in some minimum spanning tree for G,
13、 and let C = (VC, EC) be a connected component in the forest GA = (V, A). If (u, v) is a light edge connecting C to some other component in GA, then (u, v) is safe for A.,Note: Kruskal and Prims algorithms are based on the corollary., 2004 SDU 11,Idea of the Kruskal,Initialize the forest, each verte
14、x as a tree, A . Find the least weight edge (u, v) that connects any two trees in the forest. Add (u, v) to A and make the two tree as one tree, number of trees in the forest decreases 1. Repeat step 2 and 3 until A forms a spanning tree., 2004 SDU 12,Kruskals Algorithm, 2004 SDU 13,(a, d):1 (h, i):1 (c, e):1 (f, h):2 (g, h):2 (b, c):3 (b, f):3 (b, e):4 (c, d):5 (f, g):5 (e, i):6 (d, g):8 (a, b):9 (c, f):12,(a, d):1 (h, i):1 (c, e):1 (f, h):2 (g, h):2 (b, c):3 (b, f):3 (b, e):4 (c, d):5 (f, g):5 (e, i):6 (d, g):8 (a, b):9 (c, f):12, 2004 SDU 14,(a, d):1 (h, i):1 (c, e):1 (f, h):2
