최소 신장 트리 (Prim MST)

최소 신장 트리 (Minimum Spanning Tree)

주어진 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 간선들의 가중치 합이 최소인 트리

• 크러스컬(Kruskal) 알고리즘
• 프림(Prim) 알고리즘

Prim MST

임의의 점 하나를 선택 후 그 점을 기준으로 연결된 간선들 중 가중치가 가장 작은 간선을 선택해 트리에 추가

 

참고) 알기 쉬운 알고리즘

 

1. 임의의 점 하나(ex. c) 선택, 그 점에 대한 D[c] = 0으로 초기화 (여기서 D는 하나의 기준점과 나머지 점들 사이의 거리를 저장하는 배열)

2. c에서 각 점을 사이의 거리를 D[]에 저장, c에 연결되어 있는 점은 가중치로 초기화, 연결되어 있지 않은 점은 ∞로 초기화

D = [∞, 1, 0, ∞, ∞, 1] (a부터 f 순)

3. 트리는 기준점으로 잡은 c로 초기화

T = [c]

4. D에서 트리에 없는 점들 중 가중치가 가장 작은 값을 가진 점을 트리에 추가(중복값이 있으면 인덱스가 작은 값의 점을 추가)

T = [c, b]

5. 트리에 마지막으로 추가된 점 b가 기준점이 되어 D를 트리에 없는 점들에 대해서만 b와의 거리에 대한 값으로 업데이트(기존에 저장된 값보다 작을 경우에만 업데이트)

D = [3, 1, 0, 4, ∞, 1]

6. D에서 트리에 없는 점들 중 가중치가 가장 작은 값을 가진 점을 트리에 추가(중복값이 있으면 인덱스가 작은 값의 점을 추가)

T = [c, b, f]

7. 트리에 마지막으로 추가된 점 f가 기준점이 되어 D를 트리에 없는 점들에 대해서만 f와의 거리에 대한 값으로 업데이트(기존에 저장된 값보다 작을 경우에만 업데이트)

D = [3, 1, 0, 4, 9, 1]

8. D에서 트리에 없는 점들 중 가중치가 가장 작은 값을 가진 점을 트리에 추가(중복값이 있으면 인덱스가 작은 값의 점을 추가)

T = [c, b, f, a]

9. 트리에 마지막으로 추가된 점 a가 기준점이 되어 D를 트리에 없는 점들에 대해서만 a와의 거리에 대한 값으로 업데이트(기존에 저장된 값보다 작을 경우에만 업데이트)

D = [3, 1, 0, 2, 4, 1]

10. D에서 트리에 없는 점들 중 가중치가 가장 작은 값을 가진 점을 트리에 추가(중복값이 있으면 인덱스가 작은 값의 점을 추가)

T = [c, b, f, a, d]

11. 트리에 마지막으로 추가된 점 d가 기준점이 되어 D를 트리에 없는 점들에 대해서만 d와의 거리에 대한 값으로 업데이트(기존에 저장된 값보다 작을 경우에만 업데이트)

D = [3, 1, 0, 2, 4, 1]

12. D에서 트리에 없는 점들 중 가중치가 가장 작은 값을 가진 점을 트리에 추가(중복값이 있으면 인덱스가 작은 값의 점을 추가)

T = [c, b, f, a, d, e]

사이클을 고려하지 않아도 되는 이유

프림 알고리즘은 트리 밖에 있는 점을 항상 추가하므로 사이클이 만들어지지 않는다.

 

참고) 알기 쉬운 알고리즘

 

 

def GetMinVertexV0(D, T):
    vmin = -1
    mindist = float('inf')
    for v in range(len(D)):
        # T라는 Array 안에 v가 있나없나를 검사
        # T안에 있다는 건 이미 사용했다는 거니까 T에 없는 점들에 대해서만 최솟값을 구하면 됨
        # T라는 배열에 v가 없으면 안 쓴 점이니까 최솟값찾기
        if not v in T and D[v] < mindist:
            mindist = D[v]
            vmin = v
    
    return vmin


def MSTPrim(V, adj):
    vsize = len(V)
    D = [float('inf')] * vsize
    E = [0] * vsize     # E : V라는 노드가 최솟값을 가질 때 연결되는 상대 점을 담는 배열 D가 갱신될 때마다 그 시점의 vmin의 상대점을 저장
    T = []
    D[0] = 0
    
    for _ in range(vsize):
        vmin = GetMinVertexV0(D, T)
        T.append(vmin)
        
        for v in range(vsize):
            if adj[vmin][v] != None:
                if not v in T and adj[vmin][v] < D[v]:
                    D[v] = adj[vmin][v]
                    E[v] = vmin
                    print(D)
    
    return D, E



# 실행
vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
weight = [  [None,   29, None, None, None,   10, None],   # A
            [  29, None,   16, None, None, None,   15],   # B
            [None,   16, None,   12, None, None, None],   # C
            [None, None,   12, None,   22, None,   18],   # D
            [None, None, None,   22, None,   27,   25],   # E
            [  10, None, None, None,   27, None, None],   # F
            [None,   15, None,   18,   25, None, None]    # G
        ]

print("MST By Prim's Algorithm")
D, E = MSTPrim(vertex, weight)
for i in range(len(D)):
    print(f"({vertex[i]}, {vertex[E[i]]}) : {D[i]}")

 

실행 결과