Data Structures and Algorithms Spring 2022
Instructor: Chunhao Wang
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 1 / 7
Copyright By PowCoder代写 加微信 powcoder
Greedy algorithms
Greedy algorithms Warm-up
Greedy algorithms Minimum Spanning Tree
Kurskal’s Algorithm
def Kruskal MST(undirected G = (V,E), weights w = (we)e∈E): Set A := { };
for v ∈ V : make set(v);
Sort E in increasing order of edge weights; for (u,v) ∈ E:
if find set(u) ̸= find set(v): A := A ∪ {(u, v )}; union(u, v );
• make set(v): put v into a set containing itself. v → {v} • find set(u): find which set u belongs to
• union(u,v): merge the sets that u and v are in
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7
A: red edges
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 3 / 7
Proof of correctness
We need to show two things:
1. A is a spanning tree • it has no cycles
• if there exists v ∈ V that is not connected by A
then there exists e ∈ E s.t. A ∪ {e} contains no cycle then Kruskal MST will add the lightest such edge
2. A has the minimum weight. Use the cut property
Theorem (The cut property)
LetAbeasubsetofedgesofsomeMSTofG=(V,E). Let(S,V−S)beacutthat respects A. Let e be the lightest edge across the cut. Then A ∪ {e} is part of some MST
if Kruskal MST adds e = (u,v). Let S be the vertices reachable from u in A (the partial solution so far)
Then A ∪ {e} is part of some MST
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 4 / 7
Proof of the cut property theorem (I)
To prove the cut property, we need a lemma
connected and undirected graph G = (V , E ) is a tree if and only if |E | = |V | − 1
See textbook page 129
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 5 / 7
Proof of the theorem (II)
By assumption, A is a subset of edges of some MST T If e is part of T , then there is nothing to prove Ife̸∈T,wewillconstructanewMSTT′ withe∈T′:
Add e to T . This will create a cycle, which must have an edge e′ ∈ T across the cut
By definition of e, we ≤ we′
Let T′ = T ∪ {e} − {e′}. We didn’t change the edge count. Lemma =⇒ T ′ is a tree
weight(T ′) = weight(T ) + we − we′ ≤weight(T)+we′ −we′
= weight(T )
T is MST =⇒ weight(T′) = weight(T) =⇒ T′ is also an MST
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 6 / 7
Running time of Kruskal’s algorithm (I)
Depends on how we implement make set, find set, and union Using linked list:
Cost of union: O(length of the shorter list) Using an array to implement it:
vertex head
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 7 / 7
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com