Set - 경로 압축

< 쉽게 배우는 알고리즘 > 인용

 

앞에서 만든 집합을 그대로 가지고 와서 구현.

 

1. 개념

경로압축은 FindSet을 행하는 과정에서 경로의 길이를 줄이는 아이디어를 넣은 것.

FindSet을 수행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾸어준다.

이렇게 함으로써, 트리의 랭크(높이)를 줄일 가능성이 높다.

 

아래와 같이 임의의 트리가 있다고 가정해보자.

[그림 1]

위의 그림에서 FindSet(G)를 하면 아래와 같은 그림이 나오는 것을 의미한다.

[그림 2]

위의 그림과 같이, 노드G에서 루트에 이르는 경로 상에 있는 모든 노드들이

직접 루트 노드를 가리키도록 바뀌었다.

이 알고리즘에서는 함수의 리턴값을 이용하여 포인터를 갱신하고 있다.

 

FindSet(x)를 경로압축한 의사코드

아래의 함수를 쉽게 이해하려면, [그림 2]와 함께 보도록 하자.

 

 

 

 

 

 

 

 

 

 메인 함수

실행 결과

 

헤더 파일 & 소스 파일

common.h

0.00MB

main.c

0.00MB

SetTree.c

0.00MB

SetTree.h

0.00MB