[알고리즘] union-find Algorithm

 

 

union-find 알고리즘

• 사이클이 발생하는지 여부를 확인하는 방법 : 노드들의 부모가 같은지 여부를 판단 (부모 노드가 같다면 사이클 발생)
• 서로소 집합 자료구조 (Disjoint Set) : 서로소 부분 집합들로 나누어진 원소들에 대한 자료구조 (트리가 효율적)
  • 서로 연결된 두 노드 중 값이 작은 노드가 부모 노드가 됨
  • 루트 노드를 집합의 대표값으로 반환

 

 

 

union-find 연산

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

# union
def union(parent, a, b):
    a, b = find(parent, a), find(parent, b)
    if a > b:
    	parent[a] = b
    else:
    	parent[b] = a

# make-set
parent = [i for i in range(v + 1)]

• make-set(x)
  • x를 유일한 원소로 하는 집합을 생성
  • 각 노드를 루트노드
• union(x, y)
  • x와 y가 속한 두 집합을 합치는 연산
  • x와 y의 루트 노트를 찾는 법 : y를 x의 자손으로 넣음 (시간 복잡도 O(logN)으로 배열의 O(N)보다 작음)
• find(x)
  • x가 속한 집합을 찾는 연산
  • x가 속합 집합의 루트 노드를 반환 (시간 복잡도 O(logN))

 

 

 

 

최적화

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

# union
def union(parent, a, b):
    a, b = find(parent, a), find(parent, b)
    
    if a == b:
    	return
    elif rank[a] < rank[b]:
    	parent[a] = y
    elif rank[a] > rank [b]:
    	parent[b] = a
    else:
        patent[b] = a
        rank[a] += 1
    
# make-set
parent = [i for i in range(v + 1)]

# rank
rank = [0 for i in range(v + 1)]

• 최악의 경우 비대칭적 트리 (linked-list 형태) 가 될 수 있음 (이 경우 O(N))
  • 항상 높이가 더 낮은 트리를 높은 트리 밑에 넣어서 해결 가능 (union-by rank)
• 위의 코드에서 무조건 1번 이상의 재귀호출이 일어남
  • parent에 바로 갱신함으로써 해결

 

 

 

참조
 - heejeong Kwon 님의 블로그
 - YounghunJo 님의 블로그
 - 슈퍼마리호 님의 블로그