최소스패닝트리(Minimum Spanning Tree) - 프림 알고리즘, 크루스칼 알고리즘

최소스패닝트리 란?

 그래프 G에 대한 신장트리는 G의 마디를 모두 포함하면서 트리로 연결된 그래프이다. 이 중 모든 간선의 가중치가 최소가 되는 신장트리를 최소비용신장트리. 즉, 최소 스패닝 트리(MST)라고 한다.

  존재하는 신장트리를 모두 찾아보는 방법은 최악시간복잡도가 지수시간보다 나쁘기 때문에, 탐욕적 방법을 사용하면 효율적으로 문제를 풀 수 있다. 부분적으로 최적인 고려 사항에 대해 이음선을 선택하는 알고리즘으로 프림 알고리즘과 크루스칼 알고리즘이 존재한다.

 

프림 알고리즘

: 최소 스패닝 트리를 찾기 위해 정점 부분집합에 이웃한 거리들을 판단하며 구한다. 즉, 신장트리에 붙은 마디 중 가장 minimum한 값을 선택하면서 만들어가는 방식이다. 

 

알고리즘 단계

1. 하나의 꼭지점을 선택하여 이웃한 거리를 구한다.

2. 가장 최소인 이웃한 거리를 구하고, 정점 부분집합에 이웃한 정점을 추가한다.

3. 추가한 정점과 이웃한 거리들을 순회하며, 이웃한 거리를 업데이트 한다.

4. 2와 3을 반복하며, 정점 부분집합에 모든 정점이 포함되면 리턴한다.

 

소스코드

def pprint(arr):
    for line in arr:
        print(line)

# 5 7
# 0 1 1
# 0 2 3
# 1 2 3
# 1 3 6
# 2 3 4
# 2 4 2
# 3 4 5

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[float('inf')] * N for _ in range(N)]

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G[b][a] = c 

for i in range(N):
    G[i][i] = 0

pprint(G)

def prim(G, source):
    answer = []
    dist = [G[source][i] for i in range(N)]
    nearest = [0] * N

    while len(answer) < N:
        minValue = float('inf')
        vnear = 0
        
		#Find minValue
        for i in range(N):
            if 0 < dist[i] < minValue:
                minValue = dist[i]
                vnear = i
        #If Cant find minValue, then Break
        if minValue == float('inf') and vnear == 0:
            break
            
		#Append Edge        
        answer.append((vnear, minValue))
        dist[vnear] = -1

        #Update Dist
        for i in range(1, N):
            if G[i][vnear] < dist[i]:
                dist[i] = G[i][vnear]
                nearest[i] = vnear
    
    return answer


print(prim(G, 0))

 

크루스칼 알고리즘

: 최소 스패닝 트리를 찾기 위한 탐욕 알고리즘이며, 각 마디마다 자신만 포함하는 V의 서로소 부분 집합을 만드는 걸로 시작하여, 가중치가 작은 간선을 검사하여 생성하는 알고리즘이다.

 

알고리즘 단계

1. 이음선을 가중치가 작은 것부터 차례로 정렬한다.

2. 사이클이 형성되지 않는 가중치가 가장 작은 간선을 선택한다.

3. 총 V-1개의 간선이 선택 될 때까지 반복한다.

 

사이클이 형성되었는지 아닌지를 찾기 위해서 분리집합(Disjoint Set)을 사용한다. 즉, 간선이 스패닝 트리에 추가될 대 마다, Parent 관계를 만들어서 두 정점이 같은 최상위 Parent를 갖는다면 사이클이 발생함을 의미한다. 사이클이 발생하지 않는 경우에는 서로의 최상위 Parent를 연결한다.

 

또한, 작은 가중치의 이음선을 찾기위해 최소 힙을 이용한다. 소스코드는 다음과 같다.

 

소스 코드

def pprint(arr):
    for line in arr:
        print(line)
# 5 7
# 0 1 1
# 0 2 3
# 1 2 3
# 1 3 6
# 2 3 4
# 2 4 2
# 3 4 5

import sys
import heapq as hq

N, M = map(int, sys.stdin.readline().split(" "))
W = [[float('inf')] * N for _ in range(N)]
global parent
parent = [i for i in range(N)]

h = []
for _ in range(M):
    i, j, w = map(int, sys.stdin.readline().split(" "))
    hq.heappush(h, (w, i, j))

print(h)

def findRoot(x):
    if parent[x] == x:
        return x
    parent[x] = findRoot(parent[x])
    return parent[x]

def union(u, v):
    root1 = findRoot(u)
    root2 = findRoot(v)
    parent[root2] = root1

def Kruskal(heap):
    answer = []    
    while len(answer) < (N-1) and heap:
        w, i, j = hq.heappop(heap)
        print(w, i, j)
        
        if findRoot(i) == findRoot(j):
            continue
        
        union(i, j)
        answer.append((i, j, w))
        #setRoot
        print(parent)

    return answer

print(Kruskal(h))

 

Kruskal은 간선 위주이고, Prim은 정점 위주의 알고리즘이다. 그래프 내에 적은 숫자의 간선을 갖는 희소 그래프(Sparse Graph)의 경우에는 Kruskal이 적합하며, 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우에는 Prim 알고리즘이 적합하다.

 

 

 

[참조 : 최소 스패닝 트리(MST) : 크루스칼 알고리즘(Kruskal Algorithm) (https://4legs-study.tistory.com/111)]

최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm)