DOC PREVIEW
FIU COT 5407 - Chapter 23: Minimum Spanning Tree

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 )soTis 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

FIU COT 5407 - Chapter 23: Minimum Spanning Tree

Download Chapter 23: Minimum Spanning Tree
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapter 23: Minimum Spanning Tree and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapter 23: Minimum Spanning Tree 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?