[알고리즘, 파이썬] 크루스칼 알고리즘 - 2

지난 포스트에서는 크루스칼 알고리즘이 동작하는 개념에 대해서 살펴보았는데요

이번 포스트에서는 그 동작에 대한 세부적인 기준과 알고리즘을 살펴보도록 하겠습니다.

(게시글의 자료들은 잔재미코딩(https://www.fun-coding.org/Chapter20-prim-live.html) 사이트를 참조하였습니다)

 

지난 포스트에서 노드를 이를 떄 트리로 묶어 두 노드가 같은 집합인지, 다른집합인지 판단했었던것 기억하시나요? 

이를 Union-Find 알고리즘이라 하는데 그림을 통해서 다시한번 확인해 보도록 하겠습니다. 

 

Union-Find 알고리즘

• Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘
• 간단하게, 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때 (합칠 때) 사용
• Disjoint Set이란
  • 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
  • 공통 원소가 없는 (서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미함
  • Disjoint Set = 서로소 집합 자료구조

요약하자면 

initial - 각각의 집합요소들을 개별적인 집합으로 분할하는 초기화 과정 
union - 합치는 알고리즘 
find - 중복되는지 검사(사이클 검사) 

 

크루스칼은 모든 간선이 비용기준으로 정렬을해서 비용이 작은 간선부터 사이클이 생기지않는선에서 모든노드들을 연결합니다.  다만 여기서 두노드를 이었을때 사이클이 생기는지 안생기는지를 판단하기 위해서 union find알고리즘을 사용하는데,  간선끼리 이미 연결된 노드들을 부분집합으로 관리하고 특정 두노드를 뽑아서 그 노드 2개가 루트노드가 동일하다고 한다면  사이클이 생긴다고 가정 , 그게아니면 사이클이 아니라고 판단하고 union 로직을 사용해서 둘을 합친다 .

 

여기까지가 지난시간에 살펴보았던 내용이었습니다. 그렇다면 과연 Union이란 두 집합을 합치는 과정은 어떠한 기준으로 합치는 걸까요? 지난 포스트에서 막연하게 루트노드끼리 갖다 붙이라고만했지 정확한 방침이 나와있지않은데 
잘못하면 일렬로 나열하게되어 최악의 시간복잡도를 가지게 될 수도 있습니다. 

 

  특별한 기준없이 위와 같이 그저 한쪽 방향으로만 노드를 이어나가는 방식으로 트리를 구현해 보았다고 가정합시다. 위와 같이 구현하였다고 가정한다면 Union 순서에 따라 최악의 경우 링크드 리스트와 같은 형태가 될 수도 있습니다.  즉 Union, Find 동작시 계산량이 O(N)으로 트리구조를 만드는 이점이 없는 겁니다;; 이러한 사태를 방지하기위해 

nion-by-rank, path compression 기법을 사용합니다.

 

 

union-by-rank 기법

• 각 트리에 대해 높이(rank)를 기억해 두고,

• Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙임 (즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함)

• 높이가 h - 1인 두 개의 트리를 합칠 때는 한 쪽의 트리 높이를 1 증가시키고, 다른 쪽의 트리를 해당 트리에 붙임

초기화시, 모든 원소는 높이(rank) 가 0 인 개별 집합인 상태에서, 하나씩 원소를 합칠 때, union-by-rank 기법을 사용한다면,

• 높이가 h 인 트리가 만들어지려면, 높이가 h - 1 인 두 개의 트리가 합쳐져야 함
• 높이가 h - 1 인 트리를 만들기 위해 최소 n개의 원소가 필요하다면, 높이가 h 인 트리가 만들어지기 위해서는 최소 2n개의 원소가 필요함
• 따라서 union-by-rank 기법을 사용하면, union/find 연산의 시간복잡도는 O(N) 이 아닌, O(logN) 로 낮출 수 있음

 

 

path compression 기법 

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
• Find를 실행한 노드는 이후부터는 루트 노드를 한번에 알 수 있음

#참고

union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명 되었다.

• 𝑂(𝑀𝑙𝑜𝑔∗𝑁)O(Mlog∗N)
• 𝑙𝑜𝑔∗𝑁log∗N 은 다음 값을 가짐이 증명되었음
  • N이 265536265536 값을 가지더라도, 𝑙𝑜𝑔∗𝑁log∗N 의 값이 5의 값을 가지므로, 거의 O(1), 즉 상수값에 가깝다고 볼 수 있음

find 를 실행해서 해당 노드의 루트노드를 찾고, 만약 A-B-C-D로 이어진 트리가 있다면 D노드의 루트노드를 찾을 때 그 중간노드가아닌 바로 A노드를 찾아주는 것을 path compressino기법이라고 합니다.

 

무작위로 트리를 구성하였을 때 O(N)의 시간복잡도를 가졌던 것이 두 알고리즘 기법을 통해 거의 상수에 가까운 시간복잡도를 갖게 되었습니다.  위 방법들을 염두해 두고 다음 포스트에서는 드디어 크루스컬 알고리즘을 파이썬으로 구현 해 보도록 하겠습니다.