留学生考试辅导 CMPSC 465 Spring 2022 Mar 3, 2022 24 / 66

Running time of Kruskal’s algorithm (I)
Depends on how we implement make set, find set, and union
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 24 / 66

Running time of Kruskal’s algorithm (I)
Depends on how we implement make set, find set, and union Using linked list:
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 24 / 66

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 Wang CMPSC 465 Spring 2022 Mar 3, 2022 24 / 66

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 Wang CMPSC 465 Spring 2022 Mar 3, 2022 24 / 66

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 3, 2022 24 / 66

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 );
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 25 / 66

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 );
Chunhao Wang CMPSC 465 Spring 2022
Mar 3, 2022

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 );
Worst-case cost for union: O(|V |).
// O(|V|) // O(|E|log|V|)
Chunhao Wang CMPSC 465 Spring 2022
Mar 3, 2022

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
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 25 / 66

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:
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 25 / 66

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 |)
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 25 / 66

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:
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 25 / 66

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 3, 2022 25 / 66

Alternative data structure
The linked-list implementation is good enough, but there exist better data structures to improve the worst-case cost for union
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 26 / 66

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
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 26 / 66

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
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 26 / 66

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 3, 2022 26 / 66

Operations of direct tree disjoint set (I)
• make set(v)
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 27 / 66

Operations of direct tree disjoint set (I)
• make set(v)
def make set(v): π(v) := v;
rank(v) = 0;
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 27 / 66

Operations of direct tree disjoint set (I)
• make set(v)
def make set(v): π(v) := v;
rank(v) = 0; Cost: O(1)
Chunhao Wang
CMPSC 465 Spring 2022
Mar 3, 2022

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)
Chunhao Wang
CMPSC 465 Spring 2022
Mar 3, 2022

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 make set(v): while v ̸= π(v):
v := π(v);
Chunhao Wang
CMPSC 465 Spring 2022
Mar 3, 2022

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 make set(v): while v ̸= π(v):
v := π(v);
Cost: O(depth of the node in the tree)
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 27 / 66

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 make set(v): while v ̸= π(v):
v := π(v);
Cost: O(depth of the node in the tree)
• what about union?
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 27 / 66

Operations of direct tree disjoint set (II)
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 28 / 66

Operations of direct tree disjoint set (II)
Option 1 Option 2
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 28 / 66

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 3, 2022 28 / 66

Operations of direct tree disjoint set (II)
def union(x,y):
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 29 / 66

Operations of direct tree disjoint set (II)
def union(x,y):
rx := find set(x), ry := find set(y);
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 29 / 66

Operations of direct tree disjoint set (II)
def union(x,y):
rx := find set(x), ry := find set(y); if rank(rx ) > rank(ry ):
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 29 / 66

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;
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 29 / 66

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; else:
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 29 / 66

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; else:
π(rx) := ry;
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 29 / 66

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 ):
Chunhao Wang
CMPSC 465 Spring 2022
Mar 3, 2022

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;
Chunhao Wang CMPSC 465 Spring 2022 Mar 3, 2022 29 / 66

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;

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts