유니온 파인드

Life is ninanino·2022년 8월 8일
0

알고리즘

목록 보기
14/23
post-thumbnail

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 유니온 연산과
두 노드가 같은 집합에 속해 있는지를 확인하는 파인드 연산으로 구성되어 있는 알고리즘
>> 자신의 대표 노드를 찾아줌

각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화한다
find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상 시킨다

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

find(6) { 
find(5){
find(1){ ...
profile
백엔드 프로그래밍을 공부하고 있습니다. AWS, 클라우드 환경에 대해 관심이 많습니다.

0개의 댓글