그래프에서 어떤 두 노드가 서로 같은 집합에 있는지(연결되었는지) 확인하기 위해서 사용하는 알고리즘이다.

그래프에서 연결 요소(Connected Components)를 계산하거나, Disjoint-set을 구할 때, 최소 스패닝 트리를 크루스칼 알고리즘으로 구할 때 활용된다.

개념

Find 함수

Find 는 트리에서 루트 노드를 찾기 위해 구현되는 함수이다.

어떤 트리의 루트 노드를 찾는다는 뜻은, 해당 노드가 어느 집합에 포함되어 있는지 찾는 것과 같다.

노드 x 가 주어졌을 때, x의 부모 노드를 찾아갔는데 부모가 루트라면 해당 루트노드가 반환되고, 부모가 루트가 아니라면 부모의 부모를 재귀적으로 호출하여 루트노드까지 도달하게끔 구현한다.

Union 함수

Union 은 서로 다른 두 트리를 하나의 트리로 합치는 함수이다.

두 노드가 주어졌을 때, 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 것과 같다.

노드 x가 포함된 집합(x의 루트 노드)와 노드 y가 포함된 집합(y의 루트 노드)를 찾기 위해 find 함수를 사용한다.

만약에 반환받은 루트노드가 서로 다를 경우에는, 둘 중 하나의 루트노드를 다른 루트노드의 부모로 설정함으로써 두개의 트리를 합쳐준다.

두 트리를 합쳐줌으로써, 기존에 x 에 연결되어있던 노드들과 y에 연결되어있던 노드들은 find를 할 경우 같은 루트노드를 반환하게 되기 때문에 같은 집합이 되는 것이다.

일반적으로 더 낮은 높이의 트리가 다른 트리 밑으로 합쳐지게 하는데, 이를 weighted union rule 이라고 한다.

트리의 높이에 상관 없이 마구잡이로 합칠 경우에는 트리 깊이가 점점 깊어지면서, find 과정에서 루트 노드까지 탐색하는데 많은 비용이 들기 때문이다.

트리의 높이를 최소한으로 유지함으로써 탐색의 효율을 높이는 방법이다.

최적화 : Path Compression

각각의 트리가 높아질수록, 즉 자식들이 아래로 주렁주렁 매달리게 될수록, 자식마다 루트노드까지 찾아가기 위해 여러번 부모를 거쳐야 한다.

그렇기 때문에 트리의 높이를 줄일 수 있는 방법이 제시되었는데, 이를 Path Compression이라고 한다.

원리는 굉장히 간단한데, 어떤 노드를 find 함수를 통해 루트 노드를 찾아가는 과정에서, 부모를 곧바로 루트로 설정해주는 방식이다.

즉 루트-A(b의 부모)-B(c의 부모)-C 처럼 연결되는 것이 아니라, 루트-A,B,C와 같이 모든 노드들이 루트 노드의 자식으로 직접 연결된다.

만약에 그래프가 한쪽 방향으로 극단적으로 연결되어있는 구조일 때 기존 방법은 루트를 찾는데 O(N)이 걸린다면, Path Compression 을 사용할 경우 루트를 찾는데 O(1) 밖에 걸리지 않는다.

또한 트리의 높이가 다들 동일하게 유지되기 때문에, union 부분에서 트리를 합칠 때 높이를 비교하지 않아도 된다(weighted union rule 필요 없다).

구현도 Find 함수를 조금만 수정하면 되어 어렵지 않다. 코드는 아래에서 확인할 수 있다.

파이썬 코드

# parents[i] 는 i 의 부모 노드(인덱스)를 가리킴, V 는 전체 노드의 수
parents = [i for i in range(V)]

def _union(parents, x, y):
    # 두 노드의 루트를 찾은 다음,
    x = _find(parents, x)
    y = _find(parents, y)
    # 서로 다른 집합에 속해 있다면, 한쪽 집합을 다른쪽 집합의 자식으로 붙임
    # find 함수에서 경로 압축을 하기 때문에, 어느 쪽을 자식으로 붙이든 상관 없음
    if x != y:
        parents[x] = y

def _find(parents, x):
    # 부모가 자기 자신이면 루트 노드
    if parents[x] == x:
        return x
    # 루트 노드를 재귀적으로 찾고, 부모로 설정까지(Path Compression)
    parents[x] = _find(parents, parents[x])
    # 루트 노드 반환
    return parents[x]

예시

그래프에는 1 부터 8까지 총 8개 노드가 있다고 하고, 그래프 연결 상태가 아래와 같이 주어질 때, 유니온 파인드를 통해 연결 요소들을 구분지어 보자.

입력은 Edge List 로 주어진다. 즉 x y의 형태는 x 와 y 가 연결되었다는 뜻이다.

1 2
2 8
3 4
5 6
1 6

• 노드가 총 8개이므로, 처음에 parents 배열은 8개 노드 각각이 루트임을 의미하는 -1 을 담고 있다. 즉, parents = [0, 1, 2, 3, 4, 5, 6, 7, 8]. 노드 1번이 인덱스 1번으로 가게끔 하기 위해 배열의 크기는 8+1개로 설정하여 사용한다.

• 첫 입력인 1 2 를 먼저 볼 경우, 두 노드가 서로 연결되어야 한다는 의미이기 때문에 둘을 union 함수에 넣어준다.

• union 에서는 두 노드에 대해 각각 find 함수를 호출해서 루트 노드를 받아오는데, 처음엔 모두가 루트이므로 자기 자신이 반환된다.

• 두 루트(1, 2)가 서로 다르기 때문에 parents[y]] = x 를 통해 합쳐지고, parents 는 [0, 1, 1, 3, 4, 5, 6, 7, 8] 이 된다.

• 두번째 입력인 2 8 역시 두 노드를 연결하기 위해 union 에 호출되고, 8 은 find 함수로 자기 자신이 반환되지만 2 의 경우는 재귀적으로 루트까지 올라가 최종적으로 1 이 반환되며, 2 와 8 역시 합쳐져서 parents 는 [0, 1, 1, 3, 4, 5, 6, 7, 1]가 된다.

• 3번째 입력인 3 4 는 첫번째 입력과 마찬가지로 진행된다. 둘 다 루트노드이기 때문에 3이 4의 부모로써 연결된다.

• 4번째 입력인 5 6 역시 둘 다 루트노드 상태이므로 5가 6의 부모로 연결되어, 현재 parents 는 [0, 1, 1, 3, 3, 5, 5, 7, 1]이다.

• 마지막 입력인 1 6 도 union이 호출되어 find 함수를 통해, 1는 자기자신을, 6은 자신의 루트인 5를 반환하여, 1이 5의 부모로써 연결된다.

알고리즘이 종료될 경우 아래처럼 그래프가 구성되어, 각 노드들이 서로 연결이 되어있는지에 대한 여부와, 총 연결요소의 개수 등을 확인할 수 있다.

실제로 parents 에는 [0, 1, 1, 3, 3, 1, 5, 7, 1]이 저장되어 있어 사실상 노드 6은 1에 직접적으로 연결된 것이 아니라 노드 5 아래에 붙어있지만, 이는 6에 대한 find 함수가 호출될 때 루트인 1번으로 갱신될 예정이다.

즉, find(6) 이 호출될 경우 parents[x] = _find(parents, parents[x]) 부분에 의해 6번의 부모가 1로 설정되기 때문에, Path Compression이 적용된다고 볼 수 있다.