Dynamic connectivity
Connected components
- Maximal set of objects that are mutually connected.
connected(x,y)
- Find/connected query: is there a path connecting the two objects?
union(x,y)
- Union command: connect two objects.
Quick-find
is too slow for big problem
- initialize: N
- union: N
- find: 1
find: Check if p and q have the same id.
Number of array accesses (for read or write):
Union: To merge components containing p and q, change all entries whose id equals id[p] to id[q].
It takes N^2 array accesses to process a sequence of N union commands on N objects.
The maximum number of #id[] array entries that can change (from one value to a different value) during one call to union when using the quick-find data structure on n elements is n
Quick-Union
is also slow
- initialize: N
- union: N (includes cost of finding roots)
- find: N
find: Check if p and q have the same root
Number of array accesses (for read or write):
Union: To merge components containing p and q,
set the id of p's root to the id of q's root.
Weighted quick-union: (Improvement 1)
find:_Check if p and q have the same root (Identical to quick-union)
_Union: Modify quick-union to:
・Link root of smaller tree to root of larger tree.
・Update the sz[] array.
KEY POINT:
Increases by 1 when tree T1 containing x is merged into another tree T2.
- The size of the tree containing x at least doubles since | T 2 | ≥ | T 1 |.
- Size of tree containing x can double at most lg N times.
- initialize: N
- union: N (includes cost of finding roots)
- find: lgN (lg = base-2 logarithm)
Top comments (0)