[Graph] 서로소 집합

서로소 집합

• 서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합 ( 교집합이 없다 )
• 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분 ( 대표자 )
• 서로소를 표현하는 방법
  1. 연결리스트
  2. 트리 ( 사용하기 가장 편함 → 많이들 사용함 )
• 서로소 집합 연산
  1. Make-Set(x) : 먼저 각각 자신만을 원소로 갖는 집합을 구성하는 Method
  2. Find-Set(x) : 해당 Parameter의 대표자를 찾는 Method
  3. Union-Set(x, y) : 해당 파라미터의 집합이 다를 경우에 두 집합을 합침
  4. → 같은 집합인지 확인하기 위해서 Find-Set(x), Find-Set(y)를 호출

서로소 집합 표현

1. 연결 리스트
   • 같은 집합의 원소들은 하나의 연결리스트로 관리
   • 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 지정
   • 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.
2. 트리
   • 하나의 집합을 하나의 트리로 표현
   • 자식 노드가 부모 노드를 가리키고, 루트 노드가 대표자가 된다.

연결리스트로 이루어진 서로소 집합 Union

서로소 집합에 대한 연산

 1. Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산

 2. Find-Set(x) : x를 포함하는 집합을 찾는 연산

 3. Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산

 

Make-Set(x){
	parents[x] = x
}

Find-Set(x){
	if(parents[x] == x) RETURN x
	else                RETURN Find-Set(parents[x])
}

Union(x, y){
	IF Find-Set(x) == Find-Set(y) RETURN
	parents[Find-Set(y)] = Find-Set(x)
}

• 연산의 효율을 높이는 방법
  • Rank를 이용한 Union
    • 각 노드는 자신을 루트로 하는 서브 트리 높이를 Rank라는 이름으로 저장
    • 두 집합을 합칠 때 Rank가 작은 집합을 Rank가 높은 집합에 붙임
  • Path Compression
    • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꿔줌

Path Compression 적용한 Find-Set 연산

• Find-Set(x) : x를 포함하는 집합을 찾는 오퍼레이션

// 수정 전
Find-Set(x){
	if(parents[x] == x) RETURN x
	else                RETURN Find-Set(parents[x])
}

// 수정 후
Find-Set(x){
	if(parents[x] == x) RETURN x
	else                RETURN parents[x] = Find-Set(parents[x])
}

 

• Find-Set 연산은 특정 노드에서 루트까지의 경로를 찾아 가면서 노드의 부모 정보를 갱신한다. → Find-Set(x)의 연산이 많아질수록 적은 시간으로 조회가 가능하다.