# CP312 Algorithm Design and Analysis I - Lecture 13 Graph Algorithms - Minimum Spanning Trees.PDF

## Document Details

Uploaded by ZippyPelican

null

## Tags

## Summary

These notes provide an overview of graph algorithms. They cover the concepts of minimum spanning trees, including explanations of Prim's algorithm. The focus is on the specifics of the minimum spanning tree algorithms.

## Full Transcript

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