[Graph] Prim Algorithm (프림 알고리즘)

프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 O(ElogV)의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과)

---

 

개요

프림 알고리즘은 아래의 순서대로 작동한다:

1. 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
2. 그래프의 모든 변이 들어 있는 집합을 만든다.
3. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
   1. 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.

알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다.

 

 

정의 및 설명

이 알고리즘은 한 꼭짓점에서 시작한다. 트리가 모든 꼭짓점을 포함할 때까지 계속된다.

• 입력: 연결된 각 변에 가중치가 주어진 그래프 G(V, E)
• 초기화: V'={x}로 놓는다. x는 V에 있는 임의의 꼭짓점이다. E'={}로 놓는다.
• V'=V 가 될 때까지 다음을 계속 수행한다:
  • E로부터 최소의 가중치를 갖는 변 (u,v)를 뽑아낸다. 단, 이때 u는 V'에 속해야 하고 v는 V'에 속하지 말아야 한다. (같은 가중치를 갖는 여러 개의 변이 존재할 경우에는, 임의의 것을 고른다.)
  • v를 V'에 추가한다.(u,v)를 E'에 추가한다.
• 결과: 알고리즘이 종료됐을 때 만들어진 트리 ${\displaystyle G(V',E')}$가 결과가 된다. 이것은 최소 비용 신장트리가 된다.

 

구현

정점들을 방문하는 경로를 route라고 할때 route와 가장 가까운 정점을 택하여, route에 넣는 작업을 반복한다. 즉, 특정 정점과 정점 사이의 거리가 가까운 곳으로 탐색을 하는게 아니라, 경로자체와 가장 가까운 정점을 택하는 것이다.

✅ 코드1

def solution(n, costs):
    # 인접행렬 node[v][w] = d
    node = [[99999999] * n for _ in range(n)] # 초기값 무한대

    for v, w, d in costs: # 인접하면 거리 갱신
        node[v][w] = d
        node[w][v] = d

    # 탐색 경로, 방문 체크
    route = [0]
    visit = [0]*n
    visit[0] = 1

    # 최소신장트리의 길이
    result = 0

    # 모든 정점을 순회할때까지
    while len(route) < n:
        min_d = 99999999
        # 경로에 있는 정점 v
        for v in route:
            # v와 연결된 w중에서
            for w in range(n):
                # 방문하지 않았고, 가깝다면 다음 방문지로 임시 지정
                if not visit[w] and node[v][w] < min_d:
                    min_d = node[v][w]
                    min_v = w

        # 루트 자체와 가장 가까운 정점을 찾은 후
        visit[min_v] = 1 # 방문체크
        result += min_d # 길이 추가
        route.append(min_v) # 경로에 추가

    return result

print(solution(4, [[0,1,1],[0,3,2],[1,2,3],[1,3,2],[2,3,4]]))

 

✅ 코드2

V, E = map(int, input().split())
graph = [[1000000] * (V+1) for _ in range(V+1)] # 초기값 무한

for i in range(E): # 인접정점인 경우 graph 갱신
    s, e, w = map(int, input().split())
    graph[s][e] = w
    graph[e][s] = w

v = 1 # 1번부터 시작(다른데서 시작해도 값은 같음)
distance = [1000000] * (V+1) # 초기값 무한
distance[v] = 0 # 자기자신과의 거리 0
visit = [0]*(V+1)
visit[v] = 1 # 방문체크
node = 0

while node < V:
    for w in range(len(graph[v])): # 인접 정점 중에서
        if visit[w] == 0 and graph[v][w] < distance[w]: # 노방문, 거리 갱신
            distance[w] = graph[v][w]

    min_d = 1000000
    for i in range(1, V+1): # 전체 거리정보중에서
        if visit[i] == 0 and distance[i] < min_d: # 노방문 가장 가깝
            min_d = distance[i]
            v = i

    visit[v] = 1
    node += 1

print(sum(distance[1:]))

 

✅ 코드3_힙 사용

• 힙을 사용하면 노드 중 가장 짧은 곳부터 방문하기 때문에 위에 최솟값을 구했던 것을 할 필요가 없다.
• 가장 짧은 간선을 쉽게 뽑을 수 있기 때문에 힙을 사용하는 것이 더 빠르다.

from heapq import heappush, heappop

# 힙_프림 #
'''
프림은 경로 자체와 가장 가까이 있는 정점을 택하는 것
1. 처음 시작점은 0 or 1, 가중치 0으로 힙에 넣고 시작
2. 시작점과 연결된것 중 방문하지 않은 것 모두 힙에 추가
3. 위에서 추가한 정점중 가중치가 가장 작은 것으로 2번 재실행
4. 그러면 힙에 있는 값들은 (어딘가와 v의 거리, v) 이런식으로 저장된다.
5. 저 어딘가가 어디인지에 관계 없이, 작은 값을 택한다. (방문하지 않은 경우)
ㄴ 어느정점과 인접인지는 상관없다. 힙에 들어왔다는건 방문체크된 최소신장트리의 정점 중 하나와는 반드시 연결되어있기 때문.

'''
V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]

for i in range(E): # 인접정점인 경우 graph 갱신
    s, e, w = map(int, input().split())
    graph[s].append((w, e))
    graph[e].append((w, s))

visit = [0]*(V+1)
node = 0

heap = []
heappush(heap, (0, 1))

result = 0

while node < V:
    # path_to_v : 최소신장트리(경로)~v와의 거리 (선과 점의 거리랄까..?)
    path_to_v, v = heappop(heap) # 가장 가까운 값 추출

    if visit[v]: # 방문했으면 버리기 -> 이전에 더 가까운 거리로 연결한 것
        continue

    visit[v] = 1 # 방문체크
    node += 1 # 연결노드수 + 1
    result += path_to_v # 최소신장트리 가중치 추가

    for direct_v_w, w in graph[v]: # v의 인접정점 중에서
        if visit[w] == 0: # 방문하지 않은 정점에 대하여
            heappush(heap, (direct_v_w, w)) # v-w거리, w 추가

print(result)