그래프 - 유니온 파인드

유니온 파인드

일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연겨해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘

 

유니온 파인드의 핵심 이론

union, find 연산

• union 연산: 각 노드가 속한 집합을 1개로 합치는 연산입니다.
• find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산입니다.

유니온 파인드의 원리 이해하기

1. 유니온 파인드를 표현하는 방법은 1차원 리스트를 이용하는 것입니다.

처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드이므로 리스트를 자신의 인덱스 값으로 초기화 합니다.

 

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행합니다.

 

3. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산입니다.

find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 줄여줍니다.

 

find 연산의 작동 원리

1. 대상 노드 리스트에 index 값과  value 값이 동일한지 확인합니다.
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동합니다.
3. 이동 위치의 index 값과 value 값이 같을 때까지 과정1~2를 반복합니다. 반복이므로 이 부분은 재귀 함수로 구현합니다.
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경합니다.