서로소 집합

• 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 다시 말해 교집합이 없다.
• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 representative라 한다.
• 집합을 표현 하는 방법
  • 연결 리스트
  • 트리
• 상호배타 집합 연산
  • make-set(x)
  • find-set(x)
  • union(x,y)

표현

연결리스트

• 같은 집합의 원소들은 하나의 연결리스트로 관리한다
• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다
• 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다
  

트리

• 하나의 집합을 하나의 트리로 표현한다
• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다
  

연산

• make-set(x)
  • 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산

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

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

• Find-set(x)
  • x를 포함하는 집합을 찾는 연산

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

• union(x,y)
  • x와 y를 포함하는 두 집합을 통합하는 연산

def Union(x, y):
    # p[Find_Set(y)] = Find_Set(x)
    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]:
        rank[y] += 1

• Rank 를 이용한 union
  • subtree의 높이를 랭크로 저장
  • 루트에서 노드에 이르는 간선의 수를 의미
  • 이러한 방법을 사용하면 루트를 찾아가는데 필요한 연산을 최소한으로 줄여줌
• path compression
  

  찾는 h의 경로에 있는 정점들을 모두 루트 정점을 가리키게 하는 작업