서로소 집합 자료구조 . 1

 

(밑에 있는 예시를 보고 이해하기)

 

 

 

 

노드3과 노드4의 부모 노드는 다르다
여기서 두 노드가 같은 집합에 포함되어 있는지 확인하기 위해서는 각 노드의 루트노드를 찾아야 한다
노드3 : 3 --> 2 --> 1
노드4 : 4 --> 1
두 노드의 부모 노드를 따라가보니 두 노드의 루트 노드가 같으므로

두 노드는 같은 집합에 포함되어 있음을 확인할 수 있다.

 

 

 

서로소 집합 자료구조에서는 대부분 루트 노드에 바로, 즉시 접근할 수 없다
대부분 루트 노드를 찾기 위해 부모 태이블을 확인하며 계속 거슬러 올라가야 한다

 

 

 

find 함수는 특정 원소가 속한 집합을 찾기 위해 루트 노드를 반환한다
find 함수는 그 이름을 관행적으로 find_parent 라는 이름으로 짓는다

 

 

 

C++ 코드

 

 

자바 코드

 

 

 

find 함수는 재귀적으로 부모 노드를 따라가며 루트 노드를 찾기 때문에 비효율적일 때가 있다

 

 

 

노드의 부모 값이 루트 노드가 되도록 만들어 경로를 압축시킨다 

 

 

 

 

C++

 

자바

 

 

 

 

 

 

 

 

( C++, 자바 코드는 생략 )