UNION-FIND

COVER PAGE

SWE 596 FINAL ASSIGNMENT

Author: Mustafa Orkun Muti

Instructor: Prof. Dr. O. Haluk Bingöl

Topic: UNION FIND

Date: 10.02.2021

dynamic-connectivity problem

Union find problem consists of two problems

  • Union => Connecting the given two elements by edge
  • Find => Finding out if given two elements are somehow connected to each other
dynamic-connectivity problem
  • connect(4, 3)
  • connect(3, 8)
  • connect(6, 5)
  • connect(9, 4)
  • connect(2, 1)
  • isConnected(8, 9) // true
  • isConnected(5, 7) // false
  • connect(5, 0)
  • connect(7, 2)
  • connect(6, 1)
  • connect(1, 0)
  • isConnected(5, 7) // true
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
dynamic-connectivity problem

After the running the commands below:

  • connect(4, 3)
  • connect(3, 8)
  • connect(6, 5)
  • connect(9, 4)
  • connect(2, 1)
  • isConnected(8, 9) // true
  • isConnected(5, 7) // false
  • connect(5, 0)
  • connect(7, 2)
  • connect(6, 1)
  • connect(1, 0)
  • isConnected(5, 7) // true
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
modeling the elements

Applications require the modulation of all forms of elements

  • Pixels in a digital picture
  • Computers on a network
  • Friends on a web network
  • Transistors on a computer chip
  • Elements of a mathematical collection
  • Names of variables in the Fortran program
  • Metallic sites in composite structures

Is there a path connecting cyan and pink elements?

Yes, but finding the path explicitly is a harder problem

Implementing the operations

Find query. Check if there are two items in the same component.

Union command. Replace modules comprising two objects by combining them

Running the union(2,5) command on the 3 disjointed components would lead to 2 disjointed components after the process.

0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
union(2,5)
union(2,5)
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
Quick-find - eager approach

Data structure

  • Integer array id[] of length N
  • Interpretation: we can say that p and q are connected if their ids are same
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
id[]
id[]
0
0
1
1
1
1
8
8
8
8
0
0
0
0
1
1
8
8
8
8
0, 5 and 6 are connected 1, 2, and 7 are connected 3, 4, 8, and 9 are connected
0, 5 and 6 are connected 1, 2, and 7...
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
Quick-find - example

implement union(6,1)

Find => Firstly we check the ids of p and q to determine whether they are same or not

id[6] = 0; id[1] = 1. In this case, 6 and 1 are not connected

Union => To create the merge operation between components of p and q, we will change all of the entries whose id equals id[p] to id[q].

0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
id[]
id[]
0
0
1
1
1
1
8
8
8
8
0
0
0
0
1
1
8
8
8
8
after union of 6 and 1
after union of 6 and 1
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
id[]
id[]
1
1
1
1
1
1
8
8
8
8
1
1
1
1
1
1
8
8
8
8
Quick-union -lazy approach

Data Structure

  • We will create an array which has the length N, in this case we can say that parent[i] is the node which parent if o in our tree.
  • Interpretation => we will create a set consisting of all elements in the tree
  • Root of i is id[id[id[...]

Find => We check if p and q has the same parent.

0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
id[]
id[]
0
0
1
1
9
9
4
4
9
9
6
6
6
6
7
7
8
8
9
9
0
0
1
1
3
3
4
4
5
5
6
6
7
7
8
8
9
9
2
2

root of 3 is 9 root of 5 is 6

3 and 5 are not connected

root of 3 is 9 root of 5 is 6...
Quick-union - union example

Union => In order to merge p and q, we will set id of p's parent to the q's parent id

Let's implement union(3,5)

0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
id[]
id[]
0
0
1
1
9
9
4
4
9
9
6
6
6
6
7
7
8
8
6
6
0
0
1
1
3
3
4
4
5
5
6
6
7
7
8
8
9
9
2
2
Drawbacks

Algorithm cost is high in terms of array reads and writes

Quick-find problems

  • Array accesses are too high
  • It's hard to keep the tree structure flat

Quick-union problem

  • There is possibility of tree to get very tall
  • Find operations is costly caused by lots of array accesses
4
4
3
3
2
2
1
1
0
0

//worst case input
union(0,1)
union(0,2)
union(0,3)
union(0,4)

//worst case input...
Improvement 1: weighting

Weighted quick-union

To avoid the drawbacks caused by quick-find and quick-union, we implement weighting strategy

  • Update quick-union to get shorter trees
  • Save the size of each tree
  • Parent of the smaller tree will be connected to the parent of larger tree
q
q
p
p
larger
larger
smaller tree
smaller tree
tree
tree
q
q
p
p
smaller tree
smaller tree
larger
larger
tree
tree
QUICK UNION
QUICK UNION
Improvement 1: weighting

Weighted quick-union

To avoid the drawbacks caused by quick-find and quick-union, we implement weighting strategy

  • Update quick-union to get shorter trees
  • Save the size of each tree
  • Parent of the smaller tree will be connected to the parent of larger tree
q
q
p
p
larger
larger
smaller tree
smaller tree
tree
tree
p
p
larger
larger
tree
tree
WEIGHTED QUICK UNION
WEIGHTED QUICK...
q
q
smaller tree
smaller tree
Weighted quick-union analysis

Running time

  • Find => the time to find an element increases with the depth of tree
  • Union => Merging two nodes takes constant time

Assumption: max length of tree is at max logN

x
x
0
0
1
1
2
2
3
3
N= 10
N= 10
depth(x) <= logN = 3.32
depth(x) <= logN = 3.32
Weighted quick-union analysis
 algorithm initialize  union   find
 quick-find  N  N  1
 quick-union  N  N  N
 weighted QU  N  logN  logN
Weighted quick-union analysis

Weighted quick union algorithm dramatically improves the union-find operation in terms of time and space complexity and makes the problem approachable

 algorithm worst case time 
 quick-find  MN
 quick-union  MN
 weighted QU  N + M*logN
References
  1. Sedgewick, R., Wayne, K. (2011). Algorithms, 4th Edition.. Addison-Wesley. ISBN: 978-0-321-57351-3
  2. https://cse.taylor.edu/~jdenning/classes/cos265/slides/01_UnionFind.html
  3. https://www.cs.cmu.edu/~avrim/451f13/lectures/lect0912.pdf