Chapter 23: Minimum Spanning TreeLet G =(V, E) be a connected (undirected)graph. A spanning tree of G is a tree T thatconsists of edges of G and connects everypair of nodes.Let w be an integer edge-weight function. Aminimum-weight spanning-tree is a treewhose weight weight respect to w is thesmallest of all spanning trees of G.1aicfegh48762891047121411bd2Safe edges and cutsA : expandable to an MSTe ∈ E − A is safe for A if A ∪{e} : expandableto an MST or an MST alreadya cut of G : a partition (S, V − S)ofVan edge e crosses (S, V − S)ife connects anode in S and one in V − S(S, V − S) respects A ⊆ E if no edges in Across the cutbeh48628910471214117SV-SaicfdgFor any edge property Q,alight edge w.r.t.Q is one with the smallest weight amongthose with the property Q3Theorem A Let G =(V, E) be a connected(undirected) graph with edge-weight functionw.LetA be a set expandable to an MST, let(S, V − S) be a cut respecting A, and lete =(u, v) be a light edge crossing the cut.Then e is safe for A.Proof Let T be an MST containing A andnot containing e. There is a unique path ρ inT from u to v. rho has an edge crossing(S, V − S). Pick one such edge d. ThenT= T ∪{e}−{d} is a spanning tree such thatw(T)=w(T )soTis an MST and e is safe.Corollary B Every light edge connectingtwo distinct components in GA=(V, A)issafe for A.4Kruskal’s AlgorithmMaintain a collection of connectedcomponents and construct an MST A.Initially, each node is a connected componentand A = ∅.Examine all the edges in the nondecreasingorder of weights.• If the current edge connects two differentcomponents, add e to A to unite the twocomponents.The added edge is a light edge; otherwise, anedge with smaller weight should have alreadyunited the two components.5487910144216271148791014421671124879101442167112487910144216711248791014421671124879101442167112487910144216711248791014421671128888888864879101442167112487910144216711248791014421671124879101442167112487910144216711248791014421671128888887Implementation with “disjoint-sets”1 A ←∅2 for each vertex v ∈ V do3Make-Set(v)4 reorder the edges so their weights arein nondecreasing order5 for each edge (u, v) ∈ E in the order do6 ifFind-Set(u) = Find-Set(v) then7 A ← A ∪{(u, v)}8Union(u, v)9 return A8The number of disjoint-set operations thatare executed is 2E +2V − 1=O(E), out ofwhich V areMake-Set operations.So, what is the total runningtime?CSR9LaGWell, the total cost of thedisjoint-set operation isO(E lg∗V ) if the union-by-rankand the path-compressionheuristics are used.Sorting the edges requiresO(E log E) steps.We can assume E ≥ V − 1andE ≤ V2.So, it’s O(E log V ) steps.10Prim’s algorithmMaintain a set of edges A andasetofnodesB. Pick any node r as the root and set B to{r}. Set A to ∅. Then repeat the followingV − 1 times:• Find a light edge e =(u, v) connectingu ∈ B and v ∈ V − B.• Put e in A and v in B.114879101441221627114879101441221627114879101441221627114879101441221627114879101446271148791014462711487910144627114879101446271148791014462711888888888212121212112 1212121212Implementation Using a Priority QueueFor each node in Q, letkey[v]betheminimum edge weight connecting v to anode in B. By convention,key[v]=∞ if thereis no such edge.For each node v record the parent in the fieldπ[v]. This is the node u such that (u, v)isthelight edge when v is added to B.An implicit definition of A is{(v, π[v]) | v ∈ V −{r}−Q}.131 Q ← V2 for each u ∈ Q dokey[u] ←∞3key[r] ← 04 π[r] ←nil5 while Q = ∅ do6 u ←Extract-Min(Q)7 for each v ∈Adj [u] do8 if v ∈ Q and w(u, v) <key[v] then9 π[v] ← u10key[v] ← w(u, v)Line 3 forces to select r first. Lines 7-10 arefor updating the keys.Implement Q using a heap. The running timeisV · (the cost ofBuild-Heap)+(V − 1) · (the cost ofExtract-Min)+ E · (the cost ofDecrease-Key).14If either a binary heap or a binomial heap isused, the running time is:V · O(1)+(V − 1) · O(lg V )+ E · O(lg V )= O((E + V )lgV )=O(E lg E),which is the same as the running time ofKruskal’s algorithm.If a Fibonacci heap is used, the running timeis:V · O(1)+(V − 1) · O(lg V )+ E · O(1)= O(V lg V + E),which is better than the running time ofKruskal’s
View Full Document