분리 집합이란, 교집합을 갖지 않는 집합들이다. 당연하게도 분리 집합은 2 개 이상의 집합을 일컫는다.
분리 집합은 집합들 간의 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰 때 유용하다.
분리 집합은 트리 형태를 따르지만, 각 노드가 자식들을 링크하지 않고 부모를 링크한다는 점이 특이한 점이다.
또한 루트 노드가 집합 그 자체이며 집합에 이름을 부여하고자 한다면 추가 데이터를 운용해야 한다.
분리 집합의 연산은 '합집합' 과 '집합 탐색' 이 있다.
합집합 연산은 간단하게 구현된다.
A 와 B 집합의 합집합을 만들 때는 B의 루트 노드의 부모 노드를 A 의 루트 노드로 지정하면 된다.
합집합을 만들면 합쳐진 집합만 남는다.(기존의 집합이 따로 보존되지는 않음)
집합 탐색을 주의해야 하는데, 집합 탐색은 집합에서 원소를 찾는 것이 아니라 원소가 속해 있는 집합을 찾는 것이다.
(구조상 순회가 불가능하므로 분리 집합 만으로는 집합에서 원소를 찾을 수 없다.)
원소가 속해 있는 집합을 찾는 것은 간단하다. 루트 노드가 집합 그 자체이므로, 루트 노드를 찾으면 된다.
구현된 소스는 다음과 같다. 코드 하이라이트 된 것은 링크 를 참조한다.
분리 집합은 집합들 간의 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰 때 유용하다.
분리 집합은 트리 형태를 따르지만, 각 노드가 자식들을 링크하지 않고 부모를 링크한다는 점이 특이한 점이다.
또한 루트 노드가 집합 그 자체이며 집합에 이름을 부여하고자 한다면 추가 데이터를 운용해야 한다.
분리 집합의 연산은 '합집합' 과 '집합 탐색' 이 있다.
합집합 연산은 간단하게 구현된다.
A 와 B 집합의 합집합을 만들 때는 B의 루트 노드의 부모 노드를 A 의 루트 노드로 지정하면 된다.
합집합을 만들면 합쳐진 집합만 남는다.(기존의 집합이 따로 보존되지는 않음)
집합 탐색을 주의해야 하는데, 집합 탐색은 집합에서 원소를 찾는 것이 아니라 원소가 속해 있는 집합을 찾는 것이다.
(구조상 순회가 불가능하므로 분리 집합 만으로는 집합에서 원소를 찾을 수 없다.)
원소가 속해 있는 집합을 찾는 것은 간단하다. 루트 노드가 집합 그 자체이므로, 루트 노드를 찾으면 된다.
구현된 소스는 다음과 같다. 코드 하이라이트 된 것은 링크 를 참조한다.
=begin
분리 집합(DisjointSet) 을 구현한다
=end
class DisjointSet
attr_reader :data
attr_accessor :parent
def initialize(data)
@parent = nil
@data = data
end
def union_set(set)
root = find_set
set.parent = root
end
def find_set
root = self
root = root.parent while root.parent
root
end
end
a = 1;b = 2;c = 3;d = 4
set1 = DisjointSet.new(1)
set2 = DisjointSet.new(2)
set3 = DisjointSet.new(3)
set4 = DisjointSet.new(4)
puts "Set1 == Set2 : #{set1.find_set == set2.find_set}"
set1.union_set(set3)
puts "Set1 == Set3 : #{set1.find_set == set3.find_set}"
set3.union_set(set4)
puts "Set3 == Set4 : #{set3.find_set == set4.find_set}"
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| 버블 정렬 개선 - 이미 정렬되어 있는 경우 최소한의 비교로 정렬을 종료하기 (2) | 2009/05/11 |
|---|---|
| 퀵 정렬 개선 - median 을 이용한 pivot 결정하기 (0) | 2009/05/11 |
| 분리 집합 (0) | 2009/05/11 |
| 수식 트리 in Ruby (4) | 2009/05/11 |
| Backtracking : N-Queen Problem (2) | 2009/05/07 |
| Backtracking : 미로 찾기 (0) | 2009/05/07 |
