프림 알고리즘 (Prim's Algorithm, Minimum Spanning Tree)

 

프림 알고리즘은 Minimum Spanning Tree을 구하는 알고리즘이다.

Minimum Spanning Tree (MST)는

1. 그래프를 덮으면서 (spanning)
2. 비용이 가장 적은 (minimum)

트리다.

 

여담으로 최소비용 신장트리라는 말도 있는데, 말이 너무 어렵다.

최소비용 덮는트리 정도가 적당하지 않을까 생각한다.

 

프림 알고리즘은 그리디(greedy) 알고리즘이다.

MST를 구성하는 노드를 고를 때, 프림 알고리즘은 항상 최선의 선택을 한다.

여기서 최선의 선택이란 항상 비용이 가장 적은 노드를 선택하는 것을 말한다.

그리고 비용이 가장 적은 노드를 구하기 위해서 최소 힙을 사용한다.

 

MST를 구하기 위해 가장 비용이 적은 것을 선택해 나간다.

Python 구현

V를 노드(Node, or Vertex) 리스트, s를 시작 노드라 하자.

각 노드는 인접 리스트(adjacency list)를 가지고 있다.

최소 힙 구현을 위해 heapify를 사용했다.

from heapq import *

for v in V:
  v.dist = float('inf')
  v.prev = None

s.dist = 0

heapify(V)

while V:
  v = heappop(V)
  for u in v.adjs:
    if u.dist > weight(v, u):
      u.dist = weight(v, u)
      u.prev = v
      heapreplace(V, u) // Accomodate the decreased dist of u

복잡도

최소 힙을 사용해 구현하므로 시간 복잡도는 O((V+E) log V)이다.

크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘 또한 MST를 구하는 알고리즘이다.

이 알고리즘도 프림 알고리즘과 같이 그리디 알고리즘이다.

 

프림 알고리즘과 크루스칼 알고리즘은 MST를 만드는 방법이

• 한 노드를 정하고 이를 기준으로 다른 노드를 탐색해 나가는지 (프림)
• 그래프의 엣지들의 집합(서브트리)들을 병합해가는 것인지의 (크루스칼) 

차이가 있다.

 

 

크루스칼 알고리즘이 서브트리들을 병합해가는 과정

프림 알고리즘은 시작 노드에서 출발해서 최소 힙에서 노드를 하나씩 꺼내 선택한다면,

크루스칼 알고리즘은 비용 순으로 정렬된 엣지들을 순회하며, MST를 이룰 서브트리들을 만들며 병합해나간다.

 

서브트리들을 관리하기 위해서 서로소 집합(Disjoint-set)을 표현할 데이타 구조가 필요하다.

 

이 데이타 구조는

1. 집합을 트리로 표현하며, 각 노드는 부모 노드를 저장한다.
2. 루트 노드는 집합의 대표로써, 루트 노드의 이름이 집합의 이름이 된다. 루트 노드의 부모 노드는 자기 자신이다.
3. 각 노드는 서브트리의 높이를 나타내는 랭크를 가진다.

 

Disjoint Set Data Structures - GeeksforGeeks

 

이를 통해 (N이 집합의 크기라 할 때)

1. 한 노드로부터 집합 만들기 (상수 시간)
2. 한 노드가 속한 집합 찾기 (루트 노트의 이름 찾기, log N 시간)
3. 랭크를 이용해 두 집합 병합하기 (log N 시간)

연산을 구현할 수 있다.

 

크루스칼 알고리즘의 정확성은 Cut property를 이용해 증명할 수 있다.