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

수영·2022년 8월 19일

알고리즘

목록 보기

8/14

🌲스패닝 트리(Spanning Tree)

스패닝 트리란, weighted undirected(간선에 weight가 존재하고 방향성이 없는) 그래프 내의 모든 정점을 포함하는 트리를 말합니다.
그래프 내의 일부 간선들을 이용하여 만들어지며, 전체 그래프의 부분 집합이 됩니다.

👇연결 그래프

👇연결 그래프의 스패닝 트리 예시

위 그림처럼, 하나의 그래프에 대하여 여러 개의 스패닝 트리가 있을 수 있습니다.
그리고 트리라는 이름에서도 알 수 있듯 모든 정점은 포함하되 사이클이 생기면 안 되기 때문에, $N$ 개의 정점에 대해서 정확히 $N-1$ 개의 간선을 가지게 됩니다.

🎄최소 스패닝 트리(Minimum Spanning Tree)

최소 스패닝 트리란, 여러 개의 스패닝 트리 중에서 가중치의 합이 가장 작은 트리를 말합니다.

최소 스패닝 트리를 구현하는 알고리즘은 아래의 두 가지가 있습니다.

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

이 두 가지 알고리즘을 함께 알아봅시다!!

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

크루스칼 알고리즘은 그리디(Greedy) 기법을 사용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최소 스패닝 트리(MST)를 찾는 것입니다.
(최소 스패닝 트리는 그리디로 전체 최적해를 찾을 수 있음이 증명되어 있습니다.)

🤔 : 그리디라구요? 그리디는 매 순간순간 최선의 선택을 한다는 건데 어떻게 그리디로 최소 스패닝 트리를 찾죠?!
👩‍🏫 : 매 순간마다, 비용이 가장 작은 간선을 선택해서 찾을 수 있습니다!!

크루스칼 알고리즘의 동작

비용이 가장 작은 간선을 선택하기 위하여 그래프의 간선들을 오름차순으로 정렬합니다.
정렬된 간선들 중, 앞에서부터 사이클을 형성하지 않는 간선을 선택합니다.
해당 간선을 현재 최소 스패닝 트리 집합에 추가해줍니다.

크루스칼 알고리즘의 예시

가장 비용이 작은 간선을 순서대로 선택해나갑니다
단, 선택된 간선이 사이클을 만든다면, 추가하지 않습니다.

💻 크루스칼 알고리즘 구현

크루스칼 알고리즘에서 필요한 '사이클을 형성하는가'에 대한 확인은 유니온 파인드(Union-Find, Disjoint set)을 사용하여 구현합니다.

import sys
input = sys.stdin.readline

V, E = map(int, input().split()) # 노드와 간선의 개수
tree = [] # 간선들을 저장하는 리스트
for _ in range(E):
    A, B, C = map(int, input().split()) # 정점 A에서 B로 가는 비용 C 
    tree.append([A, B, C])

def find(mst, v): # 입력받은 v의 집합 대표를 찾는 함수
    if mst[v] != v:
        mst[v] = find(mst, mst[v]) # 경로 단축
    return mst[v] # v의 집합 대표 반환

def union(mst, u, v): # u의 집합과 v의 집합 합침
    up, vp = find(mst, u), find(mst, v) 
    # 더 작은 값의 대표를 합쳐진 집합의 대표로 지정
    if up < vp : 
        mst[vp] = up
    else:
        mst[up] = vp

def kruskal(tree):
    total = 0 # 총 비용
    mst = [x for x in range(V+1)] # 처음에는 각 정점이 집합의 대표
    tree.sort(key=lambda x : x[2]) # 간선의 비용 기준 오름차순 정렬

    for i in range(E): # 각 간선에 대하여 사이클 생성 확인 후 mst 추가
        a, b, c = tree[i]
        if find(mst, a) != find(mst, b): # a와 b가 같은 집합이 아니라면 union
            union(mst, a, b)
            total += c 
    return total

print(kruskal(tree))

📌프림 알고리즘(Prim Algorithm)

프림 알고리즘은 간선을 오름차순으로 선택했던 크루스칼 알고리즘과는 다르게, 시작 정점만 있는 트리로 시작하여 정점들을 추가하면서 최소 스패닝 트리를 점차 만들어가는 알고리즘입니다.
따라서, 알고리즘의 중간 과정에서도 항상 연결된 트리를 이루게 됩니다.

프림 알고리즘의 동작

시작 정점이 포함된 정점 한 개인 트리에서 시작합니다.
MST에 있는 정점과 MST에 포함되지 않은 정점 사이 간선 중 비용이 가장 작은 간선을 선택합니다.
선택된 간선과 MST에 포함되지 않았던 정점을 MST에 추가합니다.
모든 정점들이 MST에 포함될 때까지 2, 3번을 반복합니다.

프림 알고리즘의 예시

시작 정점에서 시작합니다.
보라색으로 칠해진 정점들과 아직 칠해지지 않은 정점들 사이의 최소 간선을 찾아 계속해서 트리를 확장해나가면서 MST를 형성합니다.

💻 프림 알고리즘 구현

프림 알고리즘에서 정점들 사이의 최소 간선을 찾는 과정은 우선순위 큐를 사용하여 구현할 수 있습니다.

import heapq
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
tree = {x: [] for x in range(V+1)} # 각 정점에 연결된 간선들을 저장하는 리스트
for _ in range(E):
    A, B, C = map(int, input().split()) # 정점 A에서 B로 가는 비용 C 
    tree[A].append([C, B])
    tree[B].append([C, A])

def prim(tree, start):
    total = 0 # 총 비용
    mst = set([start]) # 이미 MST에 추가된 정점 집합
    candidate = tree[start] # 우선순위 큐, 시작 정점과 연결된 간선들을 넣고 시작
    heapq.heapify(candidate) 
    while candidate :
        c, b = heapq.heappop(candidate)
        if b not in mst: # 아직 MST에 포함되지 않은 정점인 경우
            mst.add(b)
            total += c
            for w, n in tree[b]: # MST에 새롭게 추가된 정점의 간선들 우선순위 큐에 추가
                if n not in mst:
                    heapq.heappush(candidate, [w, n])
    return total

print(prim(tree, 1))