Data Structures and Algorithms Spring 2022
Instructor: Chunhao Wang
Chunhao Wang CMPSC 465 Spring 2022 Mar 17, 2022 1 / 12
Copyright By PowCoder代写 加微信 powcoder
Greedy algorithms
Greedy algorithms Minimum Spanning Tree
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 Wang CMPSC 465 Spring 2022 Mar 17, 2022 2 / 12
Running time of Kruskal’s algorithm (II)
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 );
// O(|V|) // O(|E|log|V|)
Worst-case cost for union: O(|V|). What about the cost for lines 6-9? Consider a single v ∈ V . Once it’s touched in some union operation, the size of the set at least doubles. Since the maximum size of a set can be |V |, each v is touched at most O(log |V |) times
At most |V | vertices are involved in union operations, so the total cost of
lines 6-9: O(|V | log |V |)
Total cost of the algorithm: O(|E|log|V|)
Chunhao Wang CMPSC 465 Spring 2022 Mar 17, 2022 3 / 12
Alternative data structure
The linked-list implementation is good enough, but there exist better data structures to improve the worst-case cost for union
Directed tree disjoint set:
Definition
π(x): parent of x
root node: x s.t. π(x) = x
rank(x): number of the edges in the longest simple path from x to a leaf
Chunhao Wang CMPSC 465 Spring 2022 Mar 17, 2022 4 / 12
Operations of direct tree disjoint set (I)
• make set(v)
def make set(v): π(v) := v;
rank(v) = 0;
Cost: O(1) • find set(v)
def find set(v): while v ̸= π(v):
v := π(v); return v;
Cost: O(depth of the node in the tree) • what about union?
Chunhao Wang CMPSC 465 Spring 2022 Mar 17, 2022 5 / 12
Operations of direct tree disjoint set (II)
Option 1 Option 2
Basic idea: attach the smaller ranked tree to a larger one
Chunhao Wang CMPSC 465 Spring 2022 Mar 17, 2022 6 / 12
Operations of direct tree disjoint set (II)
def union(x,y):
rx := find set(x), ry := find set(y); if rank(rx ) > rank(ry ):
π(ry) := rx;
π(rx) := ry;
if rank(rx ) == rank(ry ):
rank(ry ) := rank(ry ) + 1;
Cost: dominated by find set
Chunhao Wang CMPSC 465 Spring 2022 Mar 17, 2022 7 / 12
Cost of find set using directed tree disjoint set
Observation
Root note with rank k is formed by the merge of two rank k − 1 trees
root node of rank k has at least 2k nodes in it
By induction: base case has k = 0 and 20 = 1.
Assume the statement is true for k − 1. By observation: after merging, the number of nodes is ≥ 2k−1 + 2k−1 = 2k
By the lemma, if we have |V | nodes, the maximum rank is log |V |. So
• the cost of find set: O(log |V |) • the cost of union: O(log |V |)
Chunhao Wang CMPSC 465 Spring 2022 Mar 17, 2022 8 / 12
Total running time of Kruskal using directed tree disjoint set
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 );
Lines 6-9: O(|E|log|V|) Total cost: O(|E|log|V|)
// O(|V |) // O(|E|log|V|)
Chunhao Wang CMPSC 465 Spring 2022
Mar 17, 2022
Prim’s algorithm
Intuition: iteratively grows the tree
Chunhao Wang
CMPSC 465 Spring 2022
Mar 17, 2022 10 / 12
Prim’s algorithm: pseudocode
Let S be the set included in the tree so far
cost(v) := min we and prev(·) is used to keep track of the tree
e=(u,v) s.t. u∈S
def ST(undirected G = (V , E ), weights w = (we )e∈E ): for v ∈ V :
cost(v) := ∞; prev(v) := nil;
Pick any initial vertex u0; cost(u0) := 0;
H := make queue(V ) ; while H is not empty:
v = delete min(H); for e := (v,z) ∈ E:
if cost(z) > we: cost(z) := we;
prev(z) := v; Chunhao Wang
// keys are cost(v )
CMPSC 465 Spring 2022
Mar 17, 2022
Prim’s algorithm: a running example
Starting with f
SetS abcdefgh {} ∞/nil ∞/nil ∞/nil ∞/nil ∞/nil 0/nil ∞/nil ∞/nil
f ∞/nil ∞/nil 7/f 2/f f,d ∞/nil 8/d 7/f
f,d,g ∞/nil 8/d 7/f f,d,g,h ∞/nil 8/d 7/f
f,d,g,h,e ∞/nil 8/d 1/e f,d,g,h,e,c 8/c 8/d
f,d,g,h,e,c,b 4/b f,d,g,h,e,c,b,a
6/f ∞/nil ∞/nil 6/f 2/d 4/d
Chunhao Wang CMPSC 465 Spring 2022
Mar 17, 2022
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com