L13 - Graph Algorithms - Minimum Spanning Trees.pdf

CP312 Algorithm Design and Analysis I LECTURE 13: GRAPH ALGORITHMS – MINIMUM SPANNING TREES Minimum Spanning Tree (MST) Problem: Find a spanning tree (a tree connecting all vertices) in a graph having smallest weight. Input: A weighted connected undirected graph 𝐺 = (𝑉, 𝐸) Output: A spanning tree 𝑇...

CP312 Algorithm Design and Analysis I LECTURE 13: GRAPH ALGORITHMS – MINIMUM SPANNING TREES Minimum Spanning Tree (MST) Problem: Find a spanning tree (a tree connecting all vertices) in a graph having smallest weight. Input: A weighted connected undirected graph 𝐺 = (𝑉, 𝐸) Output: A spanning tree 𝑇 ⊆ 𝐸 such that the following is minimized: ෍ 𝑤 𝑢, 𝑣 𝑢,𝑣 ∈𝑇 Minimum Spanning Tree Example: 12 6 9 5 14 8 3 7 10 15 Minimum Spanning Tree Example: 12 6 9 5 14 8 3 7 10 15 Minimum Spanning Tree Example: 6 9 5 8 3 7 15 Minimum Spanning Tree Optimal Substructure 6 Remove any edge 𝑢, 𝑣 ∈ 𝑇 9 5 8 3 7 15 𝑇 𝐺1 Minimum Spanning Tree Optimal Substructure 𝑇1 𝑇2 6 Remove any edge 𝑢, 𝑣 ∈ 𝑇 9 Then, 𝑇 is partitioned into two subtrees 𝑇1 and 𝑇2 Theorem: 𝑇1 is a MST for 𝐺1 and 𝑇2 is a MST for 𝐺2 𝐺2 8 3 7 15 𝑇 𝐺1 Minimum Spanning Tree Theorem: 𝑇1 is a MST for 𝐺1 and 𝑇2 is a MST for 𝐺2 Proof by contradiction: 𝑇1 𝐺2 𝑇2 6 9 5 Assume that 𝑇1 is not MST for 𝐺1 𝑤 𝑇 = 𝑤 𝑢, 𝑣 + 𝑤 𝑇1 + 𝑤(𝑇2 ) ◦ Since 𝑇 is MST of 𝐺 it should have the smallest weight among all subtrees in 𝐺 𝑇1′ 𝑇1′ So, if there was another tree such that 𝑤 < ′ 𝑤(𝑇1 ) then there is a new tree 𝑇 ′ = { 𝑢, 𝑣 ∪ 𝑇1 ∪ 𝑇2 } that has weight smaller than 𝑇. Contradiction! 8 3 7 15 𝑇 Minimum Spanning Tree Optimal Substructure Do we also have overlapping subproblems? 6 ◦ YES! Great! Then dynamic programming should work. Yes, but MST exhibits another powerful property which leads to an even more efficient algorithm. 9 5 8 3 7 15 𝑇 Greedy Choice Property A locally optimal choice is globally optimal Minimum Spanning Tree Theorem: Let 𝑇 be the MST of 𝐺 = (𝑉, 𝐸) and let 𝐴 ⊆ 𝑉. Suppose that 𝑢, 𝑣 ∈ 𝐸 is the least-weight edge connecting 𝐴 to 𝑉 − 𝐴. Then 𝑢, 𝑣 ∈ 𝑇 6 9 5 8 3 7 15 𝑇 Greedy Choice Property A locally optimal choice is globally optimal Minimum Spanning Tree Theorem: Let 𝑇 be the MST of 𝐺 = (𝑉, 𝐸) and let 𝐴 ⊆ 𝑉. Suppose that 𝑢, 𝑣 ∈ 𝐸 is the least-weight edge connecting 𝐴 to 𝑉 − 𝐴. Then 𝑢, 𝑣 ∈ 𝑇 6 9 5 11 8 3 7 15 𝑇 Prim’s Algorithm Idea: At every step, mark an unvisited node 𝑣 then add the leastweight edge connecting it to the tree formed so far. MST-Prim(𝑉, 𝐸): for each 𝑢 ∈ 𝑉 𝑢. 𝑘𝑒𝑦 = ∞ 𝑢. 𝑛𝑒𝑥𝑡 = 𝑛𝑢𝑙𝑙 𝑄=𝑉 while 𝑄 ≠ ∅ 𝑢 = GET-MIN(𝑄) for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢] if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑣. 𝑘𝑒𝑦 𝑣. 𝑛𝑒𝑥𝑡 = 𝑢 𝑣. 𝑘𝑒𝑦 = 𝑤(𝑢, 𝑣) // 𝑄 is a priority-queue (e.g. min-heap) // Graph is stored as an adjacency list Prim’s Algorithm ∈𝐴 ∞ 6 ∈𝑉−𝐴 5 ∞ 14 ∞ 7 8 ∞ ∞ 3 12 ∞ 10 9 15 ∞ ∞ Prim’s Algorithm ∈𝐴 ∞ 6 ∈𝑉−𝐴 5 ∞ 14 ∞ 7 8 0 ∞ 3 12 ∞ 10 9 15 ∞ ∞ Prim’s Algorithm ∈𝐴 ∞ 6 ∈𝑉−𝐴 5 ∞ 14 8 7 7 0 ∞ 3 12 10 10 9 15 ∞ 15 Prim’s Algorithm ∈𝐴 ∞ 6 ∈𝑉−𝐴 5 ∞ 14 8 7 7 0 ∞ 3 12 10 10 9 15 ∞ 15 Prim’s Algorithm ∈𝐴 12 6 ∈𝑉−𝐴 5 5 14 8 7 7 0 ∞ 3 12 10 10 9 15 9 15 Prim’s Algorithm ∈𝐴 12 6 ∈𝑉−𝐴 5 5 14 8 7 7 0 ∞ 3 12 10 10 9 15 9 15 Prim’s Algorithm ∈𝐴 6 6 ∈𝑉−𝐴 5 5 14 7 7 8 0 14 3 12 8 10 9 15 9 15 Prim’s Algorithm ∈𝐴 6 6 ∈𝑉−𝐴 5 5 14 7 7 8 0 14 3 12 8 10 9 15 9 15 Prim’s Algorithm ∈𝐴 6 6 ∈𝑉−𝐴 5 5 14 7 7 8 0 14 3 12 8 10 9 15 9 15 Prim’s Algorithm ∈𝐴 6 6 ∈𝑉−𝐴 5 5 14 7 7 8 0 3 3 12 8 10 9 15 9 15 Prim’s Algorithm ∈𝐴 6 6 ∈𝑉−𝐴 5 5 14 7 7 8 0 3 3 12 8 10 9 15 9 15 Prim’s Algorithm ∈𝐴 6 6 ∈𝑉−𝐴 5 5 14 7 7 8 0 3 3 12 8 10 9 15 9 15 Prim’s Algorithm ∈𝐴 6 6 ∈𝑉−𝐴 5 5 14 7 7 8 0 3 3 12 8 10 9 15 9 15 Prim’s Algorithm ∈𝐴 ∈𝑉−𝐴 6 6 5 5 7 8 0 3 3 7 8 9 15 9 15 Analysis of Prim’s Algorithm Θ(|𝑉|) |𝑉| times deg(𝑢) times MST-Prim(𝑉, 𝐸): for each 𝑢 ∈ 𝑉 𝑢. 𝑘𝑒𝑦 = ∞ 𝑢. 𝑛𝑒𝑥𝑡 = 𝑛𝑢𝑙𝑙 𝑄=𝑉 while 𝑄 ≠ ∅ 𝑢 = GET-MIN(𝑄) for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢] if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑣. 𝑘𝑒𝑦 𝑣. 𝑛𝑒𝑥𝑡 = 𝑢 𝑣. 𝑘𝑒𝑦 = 𝑤(𝑢, 𝑣) // 𝑄 is a priority-queue (e.g. min-heap) // Graph is stored as an adjacency list If priority queue is a binary heap then 𝑇 𝑛 = 𝑂(𝐸 lg 𝑉) Other MST Algorithms Kruskal’s Algorithm (see the textbook) ◦ Running-time = 𝑂(𝐸 lg 𝑉) Kruskal’s Algorithm 12 6 9 5 14 8 3 7 10 15 Kruskal’s Algorithm 12 6 9 5 14 8 3 7 10 15 Kruskal’s Algorithm 12 6 9 5 14 8 3 7 10 15 Kruskal’s Algorithm 12 6 9 5 14 8 3 7 10 15 Kruskal’s Algorithm 12 6 9 5 14 8 3 7 10 15 Kruskal’s Algorithm 12 6 9 5 14 8 3 7 10 15 Kruskal’s Algorithm 12 6 9 5 14 8 3 7 10 15 Kruskal’s Algorithm 12 6 9 5 14 8 3 7 10 15 Kruskal’s Algorithm 6 9 5 8 3 7 15