Union Find 서로소 집합 알고리즘

1. 서로소 집합이란

예를들어 집합 {1,2} 와 {2, 3}은 서로소 가 아니지만 {1, 2}, {3, 4}는 서로소 집합이다.

서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.

서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다.

• union연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
• find 연산은 특정한 원소가 속한 집합이 어떤 집한 인지 알려주는 연산이다.

예를 들어 {1, 2, 3 ,4, 5, 6} 에서 서로소 부분 집합이 다음과 같이 주어진다고 가정하자

{1, 4} , {2, 3}, {2, 4}, {5, 6} 이와 같이 주어진 서로소 부분집합들은 각각 동일한 서로소 집합에 포함되어 있는 원소들이다.

위와 같은 서로소 부분 집합은 union연산을 통해 알아낼 수 있다. 위의 예시는 아래 사진과 같다.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

edges = [[1,2,29], [1,5,75],[2,3,35],[2,6,34],[3,4,7],[4,6,23],[4,7,13],[5,6,53],[6,7,25]]
v,e = 7,9
parent = [0] * (v+1)
# 부모 테이블상에서 부모를 자기 자신을 초기화
for i in range(1, v+1): parent[i] = i

test = [[1, 4], [2, 3],[2, 4], [5, 6]]
# union 연산을 각각 수행
for t in test:
    a, b = t
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
for i in range(1, v + 1):
    print(f'node {i} in {find_parent(parent, i)}')

# 부모 테이블 출력
for i in range(1, v + 1):
    print(f'node {i}s parent is {parent[i]}')