union find 알고리즘 최적화 -경로압축과 rank union-

1. 기본 union find 알고리즘의 문제점 기본적인 union find 알고리즘을 사용할 경우 union을 수행하면.. 예를 들어 최악의 경우 위와 같은 union이 형성될 수 있다. 1의 대표자를 찾을 때, 2번, 3번, 4번을 확인하고 나서야 5번을 확인하여 1의 대표자가 5이구나 라는 것을 알 수 있다 이렇게 구성되는 경우 노드의 개수가 v개이고 간선의 개수가 m개이면 최악의 경우 O(VM)이라는 비효율적인 알고리즘이 된다. 특히 모든 1,2,3,4,5의 루트 노드가 5번인데 굳이 하나씩 거슬러 올라가서 전부 확인해야하나? union 그래프가 위와 같이 구성된다면, 2,3,4의 루트 노드는 단 1번만 5를 검사하면 바로 알 수 있으므로 효율적이다. 2. 경로압축(path compression)..