union find 알고리즘

서로소 집합 알고리즘(disjoint set)

 

그래프 내에서 여러개의 node가 존재할 때

 

2개의 node를 선택해서 이 node가 서로 같은 node에 속하는지 판별하는 알고리즘

 

예를 들어 다음과 같이 8개의 node가 존재한다면

 

 

이런 경우는 부모 node가 자기 자신인 경우이다

 

 

이제 1과 2가 연결되었다고 생각해보자

 

 

이런 경우 2의 부모 node는 1이 된다

 

 

이렇게 합쳐나가는 과정을 union알고리즘이라고 부른다

 

이번엔 2와 3도 연결되었다고 가정해본다면

 

 

그러면 3의 부모 node는 2가 되는데 3과 1이 연결되었다는 것은 어떻게 아는가?

 

3의 부모 node는 2이고 2의 부모 node는 1이라서 부모 node만 보고서는 판단할 수가 없다

 

그렇지만 재귀함수를 사용하면 3의 부모 node가 2를 가리키고 2의 부모 node가 1을 가리키므로

 

결과적으로 3의 부모 node가 1을 가리킨다는 것을 파악할 수 있다

 

 

node 1,2,3의 부모 node가 모두 1을 가리키므로 1,2,3은 같은 그래프에 속한다고 볼 수 있다

 

보통 작은 값을 가진 node로 합쳐나간다.

 

find 알고리즘은 2개의 node의 부모 node가 같은지 확인하는 알고리즘이다

 

참고

 

https://m.blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)