최소 스패닝 트리(MST, Minimum Spanning Tree), Kruskal & Prim 알고리즘

Spanning Tree

스패닝 트리란 그래프 내 모든 정점을 포함하는 트리입니다.
또한, 사이클을 포함하면 안된다는 특징이 있습니다.

MST(Minimum Spanning Tree)

최소 스패닝 트리(최소 신장 트리)는 스패닝 트리 중 사용된 간선의 가중치가 최소인 트리를 뜻합니다.

MST 특징

• N개의 정점에 대해 N-1개의 간선이 존재합니다.
• 스패닝 트리이므로 사이클을 포함해서는 안됩니다.
• 간선 가중치의 합이 최소여야합니다.

MST 구현 방법

1. Kruskal 알고리즘

Greedy method를 활용하여 구현합니다.

• 간선을 가중치 기준으로 오름차순 정렬합니다.
• 사이클을 포함하지 않는 경우 MST 구성 간선으로 포함시킵니다.
• N개의 정점에 대해 N-1개의 간선을 포함시킬 때까지 반복합니다.

💻 Kruskal 코드 예시

# 두 정점의 부모 정점이 같은 지 확인하기(서로소 집합인지 확인)
def check(n):
    if n == rep[n]:
        return n
    rep[n] = check(rep[n])
    return rep[n]


# result는 MST 가중치의 합
# cnt는 간선의 개수 => 종료 조건
def kruskal():
    global result, cnt

    # 가중치를 기준으로 오름차순 정렬된 arr
    # 낮은 가중치를 가진 간선부터 연결
    for w, u, v in arr:
        # 두 정점이 서로소(사이클이 아니라면) 간선 연결 수 cnt 증가
        # u에 부모로 v 저장
        # 결과에 가중치 더하기
        if check(u) != check(v):
            cnt += 1
            rep[check(u)] = check(v)
            result += w
            if cnt == N-1:
                return

2. Prim 알고리즘

시작 정점에서부터 신장 트리를 확장해나가는 방식입니다.

• 단계별로 신장 트리를 확장합니다.
• 각 정점의 가중치에 최댓값을 저장해두고 차례대로 갱신합니다.
• 구성된 트리에서 연결 가능한 간선 중 가중치가 낮은 간선을 연결합니다.
• 모든 정점을 연결할때까지 반복합니다.

💻Prim 코드 예시

def prim(s):
    # 초기값 설정 및 방문배열 설정
    mst[s] = 0
    vst = [0] * (V+1)

    # 나머지 간선 연결(총 V+1 개 중에서 V개)
    for _ in range(V):
        # 현재 연결된 간선이 향한 정점들 중 방문하지 않았고
        # 최소값이 저장된 정점찾기
        idx = 0
        mv = INF
        for i in range(V+1):
            if vst[i] == 0 and mv > mst[i]:
                idx = i
                mv = mst[i]

        # 해당 정점에서 연결되는 간선(이미 시작점으로 사용된 정점은 제외)으로 최소값 갱신
        vst[idx] = 1
        for v, w in arr[idx]:
            if vst[v] == 0:
                mst[v] = min(mst[v], w)


V, E = map(int, input().split())

# 간선 연결하기
arr = [[] for _ in range(V+1)]
for _ in range(E):
    a, b, c = map(int, input().split())
    arr[a].append((b, c))
    arr[b].append((a, c))

# mst에 각 정점 가중치 저장 (초기 최댓값 저장)
INF = 1000001
mst = [INF] * (V+1)
prim(0)

# 최소 스패닝 트리의 가중치 합의 경우
result = sum(mst)

관련문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE&problemTitle=%EC%B5%9C%EC%86%8C+%EC%8A%A4%ED%8C%A8%EB%8B%9D&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy