Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE http://algs4.cs.princeton.edu
1.5 UNION-FIND
‣ dynamic connectivity ‣ quick find
‣ quick union
‣ improvements
‣ applications
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
are 0 and 7 connected?
FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
are 0 and 7 connected?
FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected?
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected?
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
httpc:/o/nanlegcst47.csa.npdrin2ceton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
httpc:/o/nanlegcst47.csa.npdrin2ceton.edu
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
httpc:/o/nanlegcst47.csa.npdrin2ceton.edu connect 6 and 1
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
httpc:/o/nanlegcst47.csa.npdrin2ceton.edu connect 6 and 1
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
httpc:/o/nanlegcst47.csa.npdrin2ceton.edu connect 6 and 1
connect 1 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
httpc:/o/nanlegcst47.csa.npdrin2ceton.edu connect 6 and 1
connect 1 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
1.5 QUICK-FIND DEMO
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
httpc:/o/nanlegcst47.csa.npdrin2ceton.edu connect 6 and 1
connect 1 and 0
are 0 and 7 connected?
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
Dynamic connectivity problem
G・iven a set of N objects, support two operation: ・Connect two objects.
Is there a path connecting the two objects?
connect 4 and 3
connect 3 and 8
connect 6 and 5
connect 9 and 4
01234
56789
connect 2 and 1
Algorithms
!
✔
are 0 and 7 connected?
FOURTH EDITION
are 8 and 9 connected? connect 5 and 0
ROBERT SEDGEWICK | KEVIN WAYNE
httpc:/o/nanlegcst47.csa.npdrin2ceton.edu connect 6 and 1
connect 1 and 0
are 0 and 7 connected?
✔
ROBERT SEDGEWICK | KEVIN WAYNE
4
Algorithms
A larger connectivity example
p
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
q
ROBERT SEDGEWICK | KEVIN WAYNE
5
Algorithms
A larger connectivity example
Q. Is there a path connecting p and q ?
p
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
q
ROBERT SEDGEWICK | KEVIN WAYNE
5
Algorithms
A larger connectivity example
Q. Is there a path connecting p and q ?
p
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
q
A. Yes.
ROBERT SEDGEWICK | KEVIN WAYNE
5
Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
1.5 QUICK-FIND DEMO
Quick-find demo
01234
56789
0123456789
id[]
0
1
2
3
4
5
6
7
8
9
Quick-find demo
union(4, 3)
01234
56789
0123456789
id[]
0
1
2
3
4
5
6
7
8
9
Quick-find demo
union(4, 3)
01234
56789
0123456789
id[]
0
1
2
3
4
5
6
7
8
9
Quick-find demo
union(4, 3)
01234
56789
0123456789
id[]
0
1
2
3
43
5
6
7
8
9
Quick-find demo
01234
56789
0123456789
id[]
0
1
2
3
3
5
6
7
8
9
Quick-find demo
union(3, 8)
01234
56789
0123456789
id[]
0
1
2
3
3
5
6
7
8
9
Quick-find demo
union(3, 8)
01234
56789
0123456789
id[]
0
1
2
3
3
5
6
7
8
9
Quick-find demo
union(3, 8)
01234
56789
0123456789
id[]
0
1
2
38
3
5
6
7
8
9
Quick-find demo
union(3, 8)
01234
56789
0123456789
id[]
0
1
2
38
38
5
6
7
8
9
Quick-find demo
01234
56789
0123456789
id[]
0
1
2
8
8
5
6
7
8
9
Quick-find demo
union(6, 5)
01234
56789
0123456789
id[]
0
1
2
8
8
5
6
7
8
9
Quick-find demo
union(6, 5)
01234
56789
0123456789
id[]
0
1
2
8
8
5
6
7
8
9
Quick-find demo
union(6, 5)
01234
56789
0123456789
id[]
0
1
2
8
8
5
65
7
8
9
Quick-find demo
01234
56789
0123456789
id[]
0
1
2
8
8
5
5
7
8
9
Quick-find demo
union(9, 4)
01234
56789
0123456789
id[]
0
1
2
8
8
5
5
7
8
9
Quick-find demo
union(9, 4)
01234
56789
0123456789
id[]
0
1
2
8
8
5
5
7
8
9
Quick-find demo
union(9, 4)
01234
56789
0123456789
id[]
0
1
2
8
8
5
5
7
8
98
Quick-find demo
01234
56789
0123456789
id[]
0
1
2
8
8
5
5
7
8
8
Quick-find demo
union(2, 1)
01234
56789
0123456789
id[]
0
1
2
8
8
5
5
7
8
8
Quick-find demo
union(2, 1)
01234
56789
0123456789
id[]
0
1
2
8
8
5
5
7
8
8
Quick-find demo
union(2, 1)
01234
56789
0123456789
id[]
0
1
21
8
8
5
5
7
8
8
Quick-find demo
01234
56789
0123456789
id[]
0
1
1
8
8
5
5
7
8
8
Quick-find demo
connected(8, 9)
01234
56789
0123456789
0
1
1
8
8
5
5
7
8
8
id[]
Quick-find demo
connected(8, 9)
01234
56789
0123456789
0
1
1
8
8
5
5
7
8
8
id[]
already connected
Quick-find demo
01234
56789
0123456789
id[]
0
1
1
8
8
5
5
7
8
8
Quick-find demo
connected(5, 0)
01234
56789
0123456789
0
1
1
8
8
5
5
7
8
8
id[]
Quick-find demo
connected(5, 0)
01234
56789
0123456789
0
1
1
8
8
5
5
7
8
8
id[]
not connected
Quick-find demo
01234
56789
0123456789
id[]
0
1
1
8
8
5
5
7
8
8
Quick-find demo
union(5, 0)
01234
56789
0123456789
id[]
0
1
1
8
8
5
5
7
8
8
Quick-find demo
union(5, 0)
01234
56789
0123456789
id[]
0
1
1
8
8
5
5
7
8
8
Quick-find demo
union(5, 0)
01234
56789
0123456789
id[]
0
1
1
8
8
50
5
7
8
8
Quick-find demo
union(5, 0)
01234
56789
0123456789
id[]
0
1
1
8
8
50
50
7
8
8
Quick-find demo
01234
56789
0123456789
id[]
0
1
1
8
8
0
0
7
8
8
Quick-find demo
union(7, 2)
01234
56789
0123456789
id[]
0
1
1
8
8
0
0
7
8
8
Quick-find demo
union(7, 2)
01234
56789
0123456789
id[]
0
1
1
8
8
0
0
7
8
8
Quick-find demo
union(7, 2)
01234
56789
0123456789
id[]
0
1
1
8
8
0
0
71
8
8
Quick-find demo
01234
56789
0123456789
id[]
0
1
1
8
8
0
0
1
8
8
Quick-find demo
union(6, 1)
01234
56789
0123456789
id[]
0
1
1
8
8
0
0
1
8
8
Quick-find demo
union(6, 1)
01234
56789
0123456789
id[]
0
1
1
8
8
0
0
1
8
8
Quick-find demo
union(6, 1)
01234
56789
0123456789
id[]
01
1
1
8
8
0
0
1
8
8
Quick-find demo
union(6, 1)
01234
56789
0123456789
id[]
01
1
1
8
8
01
0
1
8
8
Quick-find demo
union(6, 1)
01234
56789
0123456789
id[]
01
1
1
8
8
01
01
1
8
8
Quick-find demo
01234
56789
0123456789
id[]
1
1
1
8
8
1
1
1
8
8
Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
1.5 QUICK-UNION DEMO
Quick-union demo
0123456789
0123456789
0
1
2
3
4
5
6
7
8
9
id[]
Quick-union demo
union(4, 3)
0123456789
0123456789
0
1
2
3
4
5
6
7
8
9
id[]
Quick-union demo
union(4, 3)
0123 56789
4
0123456789
0
1
2
3
3
5
6
7
8
9
id[]
Quick-union demo
012356789
4
0123456789
0
1
2
3
3
5
6
7
8
9
id[]
Quick-union demo
union(3, 8)
012356789
4
0123456789
0
1
2
3
3
5
6
7
8
9
id[]
Quick-union demo
union(3, 8)
012 56789
3
4
0123456789
0
1
2
8
3
5
6
7
8
9
id[]
Quick-union demo
01256789
3
4
0123456789
0
1
2
8
3
5
6
7
8
9
id[]
Quick-union demo
union(6, 5)
01256789
3
4
0123456789
0
1
2
8
3
5
6
7
8
9
id[]
Quick-union demo
union(6, 5)
0125 789
63
4
0123456789
0
1
2
8
3
5
5
7
8
9
id[]
Quick-union demo
0125789
63
4
0123456789
0
1
2
8
3
5
5
7
8
9
id[]
Quick-union demo
union(9, 4)
0125789
63
4
0123456789
0
1
2
8
3
5
5
7
8
9
id[]
Quick-union demo
union(9, 4)
012578
639
4
0123456789
0
1
2
8
3
5
5
7
8
8
id[]
Quick-union demo
012578
639
4
0123456789
0
1
2
8
3
5
5
7
8
8
id[]
Quick-union demo
union(2, 1)
012578
639
4
0123456789
0
1
2
8
3
5
5
7
8
8
id[]
Quick-union demo
union(2, 1)
01 578
2639
4
0123456789
0
1
1
8
3
5
5
7
8
8
id[]
Quick-union demo
01578
2639
4
0123456789
0
1
1
8
3
5
5
7
8
8
id[]
Quick-union demo
✔
01578
2639
4
0123456789
connected(8, 9)
0
1
1
8
3
5
5
7
8
8
id[]
Quick-union demo
connected(5, 4) 𐄂 01578
2639
4
0123456789
0
1
1
8
3
5
5
7
8
8
id[]
Quick-union demo
union(5, 0)
01578
2639
4
0123456789
0
1
1
8
3
5
5
7
8
8
id[]
Quick-union demo
union(5, 0)
01 78
52 39
64
0123456789
0
1
1
8
3
0
5
7
8
8
id[]
Quick-union demo
0178
5239
64
0123456789
0
1
1
8
3
0
5
7
8
8
id[]
Quick-union demo
union(7, 2)
0178
5239
64
0123456789
0
1
1
8
3
0
5
7
8
8
id[]
Quick-union demo
union(7, 2)
018
52739
64
0123456789
0
1
1
8
3
0
5
1
8
8
id[]
Quick-union demo
018
52739
64
0123456789
0
1
1
8
3
0
5
1
8
8
id[]
Quick-union demo
union(6, 1)
018
52739
64
0123456789
0
1
1
8
3
0
5
1
8
8
id[]
Quick-union demo
union(6, 1)
18
02739
54
6
0123456789
1
1
1
8
3
0
5
1
8
8
id[]
Quick-union demo
18
02739
54
6
0123456789
1
1
1
8
3
0
5
1
8
8
id[]
Quick-union demo
union(7, 3)
18
02739
54
6
0123456789
1
1
1
8
3
0
5
1
8
8
id[]
Quick-union demo
union(7, 3)
8
139
0274
5
0123456789
1
8
1
8
3
0
5
1
8
8
6
id[]
Quick-union demo
8
139
0274
5
0123456789
1
8
1
8
3
0
5
1
8
8
6
id[]
Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
1.5 WEIGHTED QUICK-UNION
Weighted quick-union demo
0123456789
0123456789
0
1
2
3
4
5
6
7
8
9
id[]
Weighted quick-union demo
union(4, 3)
0123456789
0123456789
0
1
2
3
4
5
6
7
8
9
id[]
Weighted quick-union demo
union(4, 3)
012 456789
3
0123456789
0
1
2
4
4
5
6
7
8
9
id[]
Weighted quick-union demo
012456789
3
0123456789
0
1
2
4
4
5
6
7
8
9
id[]
Weighted quick-union demo
union(3, 8)
012456789
3
0123456789
0
1
2
4
4
5
6
7
8
9
id[]
Weighted quick-union demo
union(3, 8)
weighting: make 8 point to 4 (instead of 4 to 8)
0124567 9
38
0123456789
0
1
2
4
4
5
6
7
4
9
id[]
Weighted quick-union demo
01245679
38
0123456789
0
1
2
4
4
5
6
7
4
9
id[]
Weighted quick-union demo
union(6, 5)
01245679
38
0123456789
0
1
2
4
4
5
6
7
4
9
id[]
Weighted quick-union demo
union(6, 5)
0124 679
385
0123456789
0
1
2
4
4
6
6
7
4
9
id[]
Weighted quick-union demo
0124679
385
0123456789
0
1
2
4
4
6
6
7
4
9
id[]
Weighted quick-union demo
union(9, 4)
0124679
385
0123456789
0
1
2
4
4
6
6
7
4
9
id[]
Weighted quick-union demo
weighting: make 9 point to 4
union(9, 4)
012467
3895
0123456789
0
1
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
012467
3895
0123456789
0
1
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
union(2, 1)
012467
3895
0123456789
0
1
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
union(2, 1)
02467
13895
0123456789
0
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
02467
13895
0123456789
0
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
union(5, 0)
02467
13895
0123456789
0
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
union(5, 0)
weighting: make 0 point to 6 (instead of 6 to 0)
2467
138905
0123456789
6
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
2467
138905
0123456789
6
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
union(7, 2)
2467
138905
0123456789
6
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union demo
weighting: make 7 point to 2
union(7, 2)
246
1738905
0123456789
6
2
2
4
4
6
6
2
4
4
id[]
Weighted quick-union demo
246
17 389 05
0123456789
6
2
2
4
4
6
6
2
4
4
id[]
Weighted quick-union demo
union(6, 1)
246
17 389 05
0123456789
6
2
2
4
4
6
6
2
4
4
id[]
Weighted quick-union demo
union(6, 1)
46
389025
17
0123456789
6
2
6
4
4
6
6
2
4
4
id[]
Weighted quick-union demo
46
389 025
17
0123456789
6
2
6
4
4
6
6
2
4
4
id[]
Weighted quick-union demo
union(7, 3)
46
389 025
17
0123456789
6
2
6
4
4
6
6
2
4
4
id[]
Weighted quick-union demo
union(7, 3)
weighting: make 4 point to 6 (instead of 6 to 4)
6
4025
38917
0123456789
6
2
6
4
6
6
6
2
4
4
id[]
Weighted quick-union demo
6
4025
38917
0123456789
6
2
6
4
6
6
6
2
4
4
id[]
Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
1.5 PATH COMPRESSION
click to begin demo
Weighted quick-union with path compression demo
0123456789
0123456789
0
1
2
3
4
5
6
7
8
9
id[]
Weighted quick-union with path compression demo
union(4, 3)
0123456789
0123456789
0
1
2
3
4
5
6
7
8
9
id[]
Weighted quick-union with path compression demo
union(4, 3)
012 456789
3
0123456789
0
1
2
4
4
5
6
7
8
9
id[]
Weighted quick-union with path compression demo
012456789
3
0123456789
0
1
2
4
4
5
6
7
8
9
id[]
Weighted quick-union with path compression demo
union(3, 8)
012456789
3
0123456789
0
1
2
4
4
5
6
7
8
9
id[]
Weighted quick-union with path compression demo
union(3, 8)
0124567 9
38
0123456789
0
1
2
4
4
5
6
7
4
9
id[]
Weighted quick-union with path compression demo
01245679
38
0123456789
0
1
2
4
4
5
6
7
4
9
id[]
Weighted quick-union with path compression demo
union(6, 5)
01245679
38
0123456789
0
1
2
4
4
5
6
7
4
9
id[]
Weighted quick-union with path compression demo
union(6, 5)
0124 679
385
0123456789
0
1
2
4
4
6
6
7
4
9
id[]
Weighted quick-union with path compression demo
0124679
385
0123456789
0
1
2
4
4
6
6
7
4
9
id[]
Weighted quick-union with path compression demo
union(9, 4)
0124679
385
0123456789
0
1
2
4
4
6
6
7
4
9
id[]
Weighted quick-union with path compression demo
union(9, 4)
012467
3895
0123456789
0
1
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
012467
3895
0123456789
0
1
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
union(2, 1)
012467
3895
0123456789
0
1
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
union(2, 1)
02467
13895
0123456789
0
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
02467
13895
0123456789
0
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
union(5, 0)
02467
13895
0123456789
0
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
union(5, 0)
2467
138905
0123456789
6
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
2467
138905
0123456789
6
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
union(7, 2)
2467
138905
0123456789
6
2
2
4
4
6
6
7
4
4
id[]
Weighted quick-union with path compression demo
union(7, 2)
246
1738905
0123456789
6
2
2
4
4
6
6
2
4
4
id[]
Weighted quick-union with path compression demo
246
17 389 05
0123456789
6
2
2
4
4
6
6
2
4
4
id[]
Weighted quick-union with path compression demo
union(6, 1)
246
17 389 05
0123456789
6
2
2
4
4
6
6
2
4
4
id[]
Weighted quick-union with path compression demo
union(6, 1)
46
389025
17
0123456789
6
2
6
4
4
6
6
2
4
4
id[]
Weighted quick-union with path compression demo
46
389 025
17
0123456789
6
2
6
4
4
6
6
2
4
4
id[]
Weighted quick-union with path compression demo
union(7, 3)
46
389 025
17
0123456789
6
2
6
4
4
6
6
2
4
4
id[]
Weighted quick-union with path compression demo
union(7, 3)
path compression: make 7 point to 6
46
389 0257
1
0123456789
6
2
6
4
4
6
6
6
4
4
id[]
Weighted quick-union with path compression demo
union(7, 3)
6
40257
3891
0123456789
6
2
6
4
6
6
6
6
4
4
id[]
Weighted quick-union with path compression demo
6
40257
3891
0123456789
6
2
6
4
6
6
6
6
4
4
id[]
Weighted quick-union with path compression demo
connected(9, 1)
✔
6
40257
3891
0123456789
6
2
6
4
6
6
6
6
4
4
id[]
Weighted quick-union with path compression demo
connected(9, 1)
✔
path compression: make 9 point to 6
6
490257 381
0123456789
6
2
6
4
6
6
6
6
4
6
id[]
Weighted quick-union with path compression demo
connected(9, 1)
✔
path compression: make 1 point to 6
6
4901257 38
0123456789
6
6
6
4
6
6
6
6
4
6
id[]
Weighted quick-union with path compression demo
6
4901257 38
0123456789
6
6
6
4
6
6
6
6
4
6
id[]
Kruskal’s algorithm: running time
Proposition. Kruskal’s algorithm computes MST in time proportional to
E log E (in the worst case).
126
Kruskal’s algorithm: running time
Proposition. Kruskal’s algorithm computes MST in time proportional to
E log E (in the worst case).
Pf.
operation
frequency
time per op
build pq
1
E
delete-min
E
log E
union
V
log* V †
connected
E
log* V †
† amortized bound using weighted quick union with path compression
126
Kruskal’s algorithm: running time
Proposition. Kruskal’s algorithm computes MST in time proportional to
E log E (in the worst case).
Pf.
operation
frequency
time per op
build pq
1
E
delete-min
E
log E
union
V
log* V †
connected
E
log* V †
† amortized bound using weighted quick union with path compression
recall: log* V ≤ 5 in this universe
Remark. If edges are already sorted, order of growth is E log* V.
126
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year worst case discovered by
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
worst case discovered by
Yao
year
1975
E log log V
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
worst case discovered by
Yao Cheriton-Tarjan
year
1975
E log log V
1976
E log log V
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
worst case discovered by
Yao Cheriton-Tarjan Fredman-Tarjan
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
1986
E log (log* V)
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
1986
E log (log* V)
1997
E α(V) log α(V)
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
1986
E log (log* V)
1997
E α(V) log α(V)
2000
E α(V)
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
Chazelle
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
1986
E log (log* V)
1997
E α(V) log α(V)
2000
E α(V)
2002
optimal
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
Chazelle Pettie-Ramachandran
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
Chazelle Pettie-Ramachandran
???
1975 E log log V
1976 E log log V
1984 Elog*V, E+VlogV
1986 E log (log* V)
1997 E α(V) log α(V)
2000 E α(V)
2002 optimal
20xx
E
127
Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
Chazelle Pettie-Ramachandran
???
1975 E log log V
1976 E log log V
1984 Elog*V, E+VlogV
1986 E log (log* V)
1997 E α(V) log α(V)
2000 E α(V)
2002 optimal
20xx
E
Remark. Linear-time randomized MST algorithm (Karger-Klein-Tarjan 1995).
127