[자료구조] 프림 알고리즘 (Prim Algorithm)

프림 알고리즘이란?

: 하나의 정점에서부터 시작하여 트리를 단계적으로 확장

- 현재의 신장 트리 집합에 인접한 정점 중 최저 간선으로 연결된 정점 선택하여 신장 트리 집합에 추가

- 이 과정을 n-1개의 간선을 가질 때 까지 반복

 

과정

1> 그래프에서 시작 정점을 선택하여 초기 트리를 만든다.

2> 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택한다.

3> 이 정점 v와 이때의 간선을 트리에 추가한다.

4> 모든 정점이 삽입될 때 까지 2번으로 이동한다.

 

코드

INF = 9999

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

def MSTPrim(vertex, adj):
    vsize = len(vertex)
    dist =[INF]*vsize   # dist: [INF,INF, ...]
    selected = [False]*vsize    # selceted[False,False, ...]
    dist[0] = 0 # dist: [0, INF, INF, ...]

    for i in range(vsize):  # 정점의 수 만큼 반복
        u = getMinVertex(dist,selected)
        selected[u] = True  # u는 이제 선택됨
        print(vertex[u],end=' ')    # u를 출력
        for v in range(vsize):  # 내부 루프
            if adj[u][v] != None:   # (u,v) 간선이 있으면 dist[v] 갱신
                if selected[v] == False and adj[u][v]<dist[v]:
                    dist[v] = adj[u][v]

    print()

# 테스트 코드
vertex = ['A','B','C','D','E','F','G']

weight =[
    [None,29,None,None,None,10,None],
    [29,None,16,None,None,None,15],
    [None,16,None,12,None,None,None],
    [None,None,12,None,22,None,18],
    [None,None,None,22,None,27,25],
    [10,None,None,None,27,None,None],
    [None,15,None,18,25,None,None]
]

MSTPrim(vertex,weight)

 

시간 복잡도: O(n^2)