[CLRS] [19] disjoint set(Union-Find)

1. Disjoint set(서로소 집합)

- Disjoint set(Union Find)는 대표적인 그래프 알고리즘이다.

- 여러개의 노드가 존재할 때 두 개의 노드를 선택헤서 현재 이 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘/

 

- 해당 그래프를 표로 나타내면 다음과 같다.

0	1	2	3	4	5
0	0	0	1	4	4

 

- 이렇게 부모를 합칠 때 일반적으로 더 작은 값 쪽으로 합친다. 이를 합침(Union)이라고 한다.

 

- 하지만 해당 graph에서 3과 0이 연결되어있는지 어떻게 파악할 수 있는지가 관건이 된다.

- 0의 부모는 0 3의부모는 1이므로 '부모노드'만 보고는 한번에 파악이 불가능이다. --> 그렇기에 재귀함수를 이용하여 해결 가능하다.

ex)

3의 부모노드 -> 1
1의 부모노드 -> 0

0의 부모노드 == (3의 부모노드)의 부모노드 

이렇게 끝까지 내려가서 같다면 같은 graph에 있다는 것이 자명해진다.

이를 Find라고 한다.

 

2. Code 구현

def getParent(parent,x):
    if parent[x] == x:
        return x
    else:
        parent[x] = getParent(parent,parent[x])
        return parent[x]

def unionParent(parent,a,b):
    a = getParent(parent,a)
    b = getParent(parent,b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def findParent(parent,a,b):
    a = getParent(parent,a)
    b = getParent(parent,b)
    if a==b:
        return True
    return False

#example
parent = [x for x in range(6)]

unionParent(parent,0,1)
unionParent(parent,0,2)
unionParent(parent,1,3)
unionParent(parent,4,5)

print(findParent(parent,4,0))
print(findParent(parent,3,2))


--------------------------------------------
Output

False
True