Union-Find Algorithm — Python

Union-Find

1. When?

To check whether unconnected two different nodes are in same set!

If I want to check if ‘A’ and ‘B’ is connected (there are number of N nodes
Time complexity is O(logN)
Space complexity is O(N)

Super fast way!!

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

2. Process

i) initialize

Assuming we have a total of seven nodes connected like this.
Initialize parent to itself

You can make this by Python code

# number of nodes: N
parent = [0] * (N + 1)

for i in range(1, N + 1) :
 parent[i] = i

ii) union

Next we need to find the connected one.
Given the condition that ‘A’ and ‘B’ are connected,
find and compare their each parent
follow the parent of larger value to the parent of the smaller value

Parent after initialize

This is the parent after the initialize.

Get leedohyung28’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In there if we want to know 5,6,7 is connected (union)
6’s parent have to be 5,
and 7’s parent have to be 6.

Parent after find union

You can find union by Python code like this

def unionParent(a, b) :
 a = findParent(a)
    b = findParent(b)
    if a > b :
     parent[a] = b
    else :
     parent[a] = b

To do this, we’d need to run the linked condition like this.

# link e = [[5,6], [6,7]]
for i in e :
 a, b = i[0], i[1]
    unionParent(a,b)

In this how can we find Parent?

iii) find

To find parent(root) node, you can write Python code like this

def findParent(x) :
 
   # Recursion until find root (highest) node
   if parent[x] != x :
       return findParent(parent[x])
      return x

If root node is myself, it will return ‘x’ (myself literally)
but if I have parent, it will return parent

After combination, parent node will be like

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

3. Can we make faster? (Optimize)

i) Path compression

When we find parent of this by previous method it could be,

however, if the parent could be like this, isn’t it can be more faster?

parent after path compression

You can make this by Python code

def find(x) :
 if parent[x] != x :
     parent[x] = find(parent[x])
    
    # will return the last parent (root) node
    return parent[x]

ii) Union by Rank

If there are two linked nodes with different ranks,
you can reduce the height of tree by union them in order of increasing rank.

You can make this by Python code

def union(a, b) :
 n1 = find(a)
    n2 = find(b)
    
    # if they are in same tree (set)
    if n1 == n2 :
     return
        
    # smaller ranked tree is attached to larger ranked tree
    if rank[n1] > rank[n2] :
     parent[n2] = n1
    elif rank[n1] < rank[n2] :
     parent[n1] = n2
    
    # if rank is same, randomly attach to n1 and increase rank
    else :
     parent[n2] = n1
        rank[n1] += 1 

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

4. Compare with Other algorithms

Kruskal Algorithm : Connecting all vertexs at the least cost.
(One vertex to Others)
- Minimum Spanning Tree
- Time complexity : O(ElogE)
- If we don’t need cost Union-Find is better.

Floyd-Warshall Algorithmh : Conecting all vertexs at the least cost.
(All vertex to All Vertex)
- Time complexity : O(E³)
- If we don’t need cost Union-Find is better.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

In conclusion

If we want to find two different nodes without cost
Union-Find is the best way👍