Algorithm. 그래프 - 상호배타 집합

1. 서로소 또는 상호배타 집합(Disjoint set)

• 교집합이 없는 집합
• 집합에 속한 특정 원소로 각 집합을 구분
  • 대표자(representative)
• 상호배타 집합 표현
  • 연결 리스트, 트리

2. 상호배타 집합 연산

• Make-Set(x) : 원소 x만 속한 집합을 생성
• Find-Set9x) : 원소 x가 속한 집합을 알아내는 연산, 해당 집합의 대표자를 반환
• Union(x, y) : 원소 x가 속한 집합과 원소 y가 속한 집합을 합치는 연산, 대표자는 본인이 설정

3. 연결 리스트 표현

• 같은 집합의 원소들을 하나의 연결 리스트로 관리
• 연결리스트의 첫번째 원소가 집합의 대표원소
• 각 원소는 대표원소를 가리키는 링크를 갖는다.

세 개의 상호배타 집합

4. 트리 표현

• 집합(disjoint set)을 하나의 트리로 표현
• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표원소가 된다.

세 개의 상호배타 집합

연산 알고리즘

Make_Set(x)

def Make_Set(x):
	p[x] = x

 

Find_Set(x)

def Find_Set(x):
    if x == p[x] : return x
    else : return Find_Set(p[x])

 

Union(x, y)

def Union(x, y):
	p[Find_Set(y)] = Find_Set(x)

 

5. 트리 표현의 문제점

• 편향 트리가 생성될 수 있다.
• 모든 원소들이 루트를 부모로 가리키도록 해서 해결한다.

1. 두 집합을 합칠 때 rank(트리의 높이)가 낮은 집합을 rank가 높은 집합에 붙인다.

2. Find-Set 과정에서 만나는 모든 노드들이 root를 가리키도록 부모 정보 변경

 

효율적인 연산 알고리즘

Make_Set(x)

# p[x] : 노드 x의 부모 저장
# rank[x] : 루트 노드가 x인 트리의 랭크 값 저장

def Make_Set(x):
    p[x] = x # 자기자신
    rank[x] = 0

Find_Set(x)

def Find_Set(x):
    if x != p[x]: # x가 루트가 아닌경우
    	p[x] = Find_Set(p[x]) # Path Compression
    return p[x]

 Union(x, y)

def Union(x, y):
    Link(Find_Set(x), Find_Set(y))

def Link(x, y):
    if rank[x] > rank[y]:
    	p[y] = x
    else:
    	p[x] = y
    if rank[x] == rank[y]: # x와 y의 rank값이 같다면 y를 루트로 설정하고 rank를 1증가시킨다
    	rank[y] += 1

 

상호배타 집합 알고리즘은 크루스칼 최소 신장 트리(Kruskal Minimum Spanning Tree, MST) 알고리즘에 쓰인다.