CS代写 MPSC 465 Spring 2022 Mar 15, 2022 1 / 7

Data Structures and Algorithms Spring 2022
Instructor: Chunhao Wang
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 1 / 7

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):
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7

Kurskal’s Algorithm
def Kruskal MST(undirected G = (V,E), weights w = (we)e∈E): Set A := { };
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7

Kurskal’s Algorithm
def Kruskal MST(undirected G = (V,E), weights w = (we)e∈E): Set A := { };
for v ∈ V :
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7

Kurskal’s Algorithm
def Kruskal MST(undirected G = (V,E), weights w = (we)e∈E): Set A := { };
for v ∈ V : make set(v);
• make set(v): put v into a set containing itself. v 􏰁→ {v}
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7

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;
• make set(v): put v into a set containing itself. v 􏰁→ {v}
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7

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:
• make set(v): put v into a set containing itself. v 􏰁→ {v}
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7

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):
• make set(v): put v into a set containing itself. v 􏰁→ {v} • find set(u): find which set u belongs to
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7

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 )};
• make set(v): put v into a set containing itself. v 􏰁→ {v} • find set(u): find which set u belongs to
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 2 / 7

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:
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 4 / 7

Proof of correctness
We need to show two things: 1. A is a spanning tree
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 4 / 7

Proof of correctness
We need to show two things:
1. A is a spanning tree • it has no cycles
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 4 / 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
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 4 / 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
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
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 5 / 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
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 6 / 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
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 6 / 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′:
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 6 / 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.
Chunhao Wang
CMPSC 465 Spring 2022 Mar 15, 2022 6 / 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
Chunhao Wang
CMPSC 465 Spring 2022 Mar 15, 2022 6 / 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′
Chunhao Wang
CMPSC 465 Spring 2022 Mar 15, 2022 6 / 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′
Chunhao Wang
CMPSC 465 Spring 2022 Mar 15, 2022 6 / 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 )
Chunhao Wang
CMPSC 465 Spring 2022
Mar 15, 2022 6 / 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′
T is MST =⇒ weight(T ′) = weight(T ) Chunhao MPSC 465 Spring 2022
Mar 15, 2022 6 / 7
= weight(T )

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
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 7 / 7

Running time of Kruskal’s algorithm (I)
Depends on how we implement make set, find set, and union Using linked list:
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 7 / 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:
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 7 / 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)
Chunhao MPSC 465 Spring 2022 Mar 15, 2022 7 / 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

Related Posts