MST:The abstract problem Input:A connected weighted graph 4 1 口G=(V,E),w:E→R. Output:A spanning tree 4 6 3 with min total weight. 2 2 ▣A spanning tree whose weight is the minimum of 2 3 that of all spanning trees. Any algorithm? 6
MST: The abstract problem ◼ Input: A connected weighted graph ❑ 𝐺 = (𝑉, 𝐸), 𝑤: 𝐸 → ℝ. ◼ Output: A spanning tree with min total weight. ❑ A spanning tree whose weight is the minimum of that of all spanning trees. ◼ Any algorithm? 4 1 4 3 5 4 2 2 2 3 3 2 6 6
Methodology 4:Starting from a naive solution 0 See whether it works well enough If not,try to improve it. A first attempt may not be correct ■ But that's fine.The key is that it'll give you a chance to understand the problem
◼ Methodology 4: Starting from a naïve solution ❑ See whether it works well enough ❑ If not, try to improve it. ◼ A first attempt may not be correct ◼ But that’s fine. The key is that it’ll give you a chance to understand the problem. 7
What if I'm really stingy? I'll first pick the cheapest edge. I'll then again pick the cheapest one in the remaining edges 6 1 I'll just keep doing like this .. 5 6 3 as long as no cycle caused ..until a cycle is unavoidable. 4 Then I've got a spanning tree! No cycle. Connected:Otherwise I can still pick something without causing a cycle. Concern:Is there a better spanning tree? 8
What if I’m really stingy? ◼ I’ll first pick the cheapest edge. ◼ I’ll then again pick the cheapest one in the remaining edges ◼ I’ll just keep doing like this … ❑ as long as no cycle caused ◼ … until a cycle is unavoidable. Then I’ve got a spanning tree! ❑ No cycle. ❑ Connected: Otherwise I can still pick something without causing a cycle. ◼ Concern: Is there a better spanning tree? 6 1 5 4 6 5 4 2 4 3 4 2 6 8
Kruskal's Algorithm What we did just now is Kruskal's algorithm. Repeatedly add the next lightest edge that doesn't produce a cycle... in case of a tie,break it arbitrarily ...until finally reaching a tree ---that's the answer!
Kruskal's Algorithm ◼ What we did just now is Kruskal’s algorithm. ❑ Repeatedly add the next lightest edge that doesn't produce a cycle… ◼ in case of a tie, break it arbitrarily. ❑ …until finally reaching a tree --- that’s the answer! 9
Illustrate an execution of the algorithm -At first all vertices are all separated. Little by little,they merge 5 into groups. Groups merge into larger groups. Finally,all groups merge into one. o That's the spanning tree outputted by the algorithm. 10
Illustrate an execution of the algorithm ◼ At first all vertices are all separated. ◼ Little by little, they merge into groups. ◼ Groups merge into larger groups. ◼ Finally, all groups merge into one. ◼ That’s the spanning tree outputted by the algorithm. 6 1 5 4 6 5 4 2 4 3 4 2 6 10