알고리즘 - 최소 비용 신장 트리

최소 비용 신장 트리 (최소 신장 트리: MST: Minimum Spanning Tree)

• 그래프의 모든 정점은 연결되어야 합니다

• 연결에 필요한 간선의 가중치 합(비용)이 최소가 되어야 합니다

• 최소 비용 신장 트리: 가중치 그래프의 여러 신장 트리 중에서 간선의 가중치 합이 최소인 것

MST의 응용 분야

• 통신망: 모든 사이트가 연결되도록 하면서 비용을 최소화하는 문제
• 도로망: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
• 배관 작업: 파이프를 모두 연결하면서 파이프의 길이를 최소화하는 문제
• 전기 회로: 단자들을 모두 연결하면서 전선의 길이를 최소화하는 문제

MST에 포함되지 않은 최소 dist의 정점 찾기

INF = 999
def getMinVertex(dist, selected):
    minv = 0
    mindist = INF
    for v in range(len(dist)):
        if selected[v] == False and dist[v] < mindist:
            mindist = dist[v]
            minv = v
    return minv     

프림의 최소 신장 트리 알고리즘

def MSTprim(vertex, adj):
    n = len(vertex)
    dist = [INF] * n
    dist[0] = 0
    selected = [False] * n

    for _ in range(n):              # n개의 정점을 MST에 추가하면 종료됨
        u = getMinVertx(dist, selected)
        selected[u] = True
        print(vertex[u], end= ' ')
        for v in range(n):
                                    # 간선 (u, v) 가 있고, v가 MST에 포함안되면
            if adj[u][v] != INF and not selected[v]:
                if adj[u][v] < dist[v]: # (u,v)가 dist[v] 보다 작으면
                    dist[v] = adj[u][v] # dist[v] 갱신

        print(': ', dist)     # 중간 결과 출력
            

실행 결과

A : [0, 25, 999, 12, 999, 999, 999] 
D : [0, 25, 999, 12, 17, 37, 999]
E : [0, 15, 999, 12, 17, 19 ,14]
G : [0, 15, 16, 12, 17, 19, 14]
B : [0, 15, 10, 12, 17, 19, 14]
C : [0, 15, 10, 12, 17, 19, 14]
F : [0, 15, 10, 12, 17, 19, 14]

프림 알고리즘은 얼마나 빠를까?

• 외부 루프는 정점의 수 $n$만큼 반복
• 내부에서는 18행의 getMinVertex() 함수에 반복문이 있는데, 역시 $n$번 반복
• 또한 21행의 내부 루프도 $n$번 반복
• 따라서 외부와 내부 루프의 반복 횟수의 곱에 비례하는 연산이 필요
• 시간 복잡도는 $O(n^2)$ 이다