알고-리즘/MST

Borůvka's Algorithm

Signoid 2024. 3. 16. 23:38
반응형

1. 개요

MST(Minimum Spanning Tree), MSF(Minimum Spanning Forst)를 얻기 위해 사용하는 탑욕법 기반의 알고리즘이다.

처음으로 제시된 것은 1926년에 Otakar Borůvka에 의해 고안된 알고리즘으로, 체코에 있는 Moravia의 전력망 건설을 효율적으로 하기 위한 방식으로 제안되었다.

(꽤나 신기한 이유에 의해 고안된 알고리즘이라 생각된다. 사실 네트워크 연결이나... 전력망 연결이나... 거의 비슷한 느낌으로 연결하니까 그럴 법도 하다 생각된다.)

2. 과정

입력은 서로 연결된, 가중치가 존재하는 무향 그래프를 입력으로 받는다.

    1. 입력으로 받은 그래프의 정점들을 하나씩  forest T에 넣어 초기화한다.
    2. T 가 하나보다 많은 요소를 갖고 있을 경우(minimum spanning tree가 형성되지 않은 경우)
      1. T에 속한 요소 C에 대해 반복을 진행한다.
        1. 간선 집합 S를 비어있는 집합으로 생성하고
        2. C에 속한 정점 v에 대해 반복을 진행한다.
          1.  C에 속한 정점 v에서 C외부로 이어지는 가장 낮은 가중치의 간선을 S에 추가한다.
        3. S에 속한 값들 중 최소값을 T에 추가하여 더 큰component를 구성한다.

3. 복잡도

Borůvka 알고리즘은, 정점의 개수를 2로 나눈 수만큼 계속 탐색 공간이 적어지므로,  $\log V$만큼의 반복을 진행한다.

각 반복마다 최대 간선의 수만큼 반복하므로, 이를 식으로 나타내면 $C|E|\log|V|$의 수치가 나오게 된다.

이때, 이를 점근적 상한인 O 표기법으로 나타내면 $O(|E|\log|V|)$의 값이 나오게 되며 이 값이 Borůvka알고리즘의 시간복잡도가 된다.

4. 여담

prim알고리즘과 비슷하게 greedy 한 방식으로 진행되는 알고리즘으로 prim 알고리즘이 binary heap을 사용한 경우, $O(|E|\log|V|)$인것과 동일한 성능을 가진다. (맨 처음 나왔을 때는 binary heap이 없었으므로... 실상은 Borůvka 알고리즘의 승이다.)

 prim 알고리즘은 fibonacci heap을 사용할 경우 그 성능이 또 다시 달라지는데 $O(|E| + |V|\log|V|)$이다. $V$가 적고 간선이 많은 상태라면 충분히 강점이 있지만... Borůvka 알고리즘의 경우,  soft heap과 decision tree를 활용하여$O(|E|\cdot\alpha(m,n)), where\,\alpha(m, n) =  Inverse\,of\,Ackermann-Péter\,func$인 최적의 시간복잡도를 갖는 알고리즘에 활용되므로 시간복잡도 측면에서 Borůvka 알고리즘의 승리라고 볼 수 있겠다.

#상당히 파이썬으로 구현이 까다롭다...

#구현이 완료되는대로 구현된 내용과 알고리즘에서 기본적으로 다루는 개념들에 대해 업데이트할 예정이다. 

 

반응형