算法课件Lecture5章节.pptVIP

Lecture 5Minimum Spanning Tree 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. Every foot of cable costs us $1 We want the cheapest possible network. Minimum Spanning Tree--The Definition Minimum Spanning Tree Problem 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 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 Kruskal’s and Prim’s algorithms are implementations of the generic algorithm on how to maintain A and find the safe edge (u, v) for A. A Generic Algorithm Related Notions Determine Safe Edges for A Theorem 23.1 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, 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. 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, 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. Idea of the Kruskal Initialize the forest, each vertex 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. Kruskal’s Algorithm Time Complexity Analysis Correctness Proof Correctness Proof(Continued)