프림 알고리즘

프림 알고리즘은 여러 지점을 하나로 잇는 선들 가운데 비용 합이 가장 작은 묶음을 골라 줍니다. 한 지점에서 시작해 지금까지 이은 지점들에 가장 싸게 붙는 선을 하나씩 더합니다. 모든 지점이 이어지면 끝납니다.

상세

이 절은 프림 알고리즘이 무엇을 받아 무엇을 내는지부터 봅니다. 그다음 노드 다섯 개짜리 작은 그래프 하나로 절차를 끝까지 따라갑니다. 답이 왜 맞는지, 얼마나 걸리는지, 닮은 알고리즘과 무엇이 다른지는 그 뒤에 봅니다.

이름은 이 절차를 발표한 미국의 수학자 로버트 프림(Robert C. Prim)에게서 왔습니다. 체코의 수학자 보이테흐 야르니크(Vojtěch Jarník)가 먼저 같은 절차를 내놓아서 야르니크 알고리즘이라고도 부릅니다.

넣는 것과 나오는 것

프림 알고리즘은 그래프 위에서 돕니다. 그래프는 점과 그 점들을 잇는 선으로 관계를 나타낸 구조입니다. 마을과 케이블 구간처럼 무엇과 무엇이 이어질 수 있는지를 담습니다.

점을 노드, 선을 간선이라고 합니다. 케이블 예라면 마을이 노드, 놓을 수 있는 구간이 간선입니다.

간선마다 붙은 숫자는 가중치입니다. 그 간선을 쓰는 비용을 뜻합니다. 케이블 예라면 그 구간의 공사비가 가중치입니다.

프림 알고리즘이 받는 그래프의 간선에는 방향이 없습니다. A 와 B 를 잇는 케이블은 어느 쪽에서 봐도 같은 케이블이기 때문입니다. 이런 그래프를 무방향 그래프라고 합니다.

그래프는 한 덩어리로 이어져 있어야 합니다. 어느 노드에서 출발해도 간선을 따라 다른 모든 노드에 닿을 수 있다는 뜻입니다. 이런 그래프를 연결 그래프라고 합니다. 애초에 이을 수 없는 마을이 있으면 모두 잇는 답도 없습니다.

답의 모양은 트리

간선을 따라가다 출발한 노드로 되돌아오는 고리를 사이클이라고 합니다. A 에서 B, B 에서 C, C 에서 다시 A 로 오는 길이 사이클입니다.

모든 노드가 이어져 있으면서 사이클이 없는 그래프를 트리라고 합니다. 노드가 V 개인 트리는 간선이 늘 V − 1 개입니다. 간선을 하나 빼면 끊기고, 하나 더하면 사이클이 생깁니다.

케이블 공사의 답은 트리 모양이어야 합니다. 사이클이 있으면 그 고리에서 구간 하나를 빼도 마을들은 여전히 이어집니다. 그 구간의 공사비만 헛돈이 됩니다.

원래 그래프의 노드를 모두 담으면서 간선은 일부만 골라 만든 트리를 신장 트리라고 합니다. 신장 트리 가운데 가중치 합이 가장 작은 것이 최소 신장 트리입니다. 프림 알고리즘이 내는 것이 이것입니다.

정리하면 넣는 것은 연결된 무방향 그래프와 출발 노드 하나입니다. 나오는 것은 최소 신장 트리를 이루는 간선 V − 1 개입니다. 출발 노드를 어디로 잡아도 가중치 합은 같습니다.

예시로 쓸 그래프

절차를 따라갈 그래프는 아래와 같습니다. 노드는 A · B · C · D · E 다섯 개, 간선은 일곱 개입니다. 선 위의 숫자가 가중치입니다.

flowchart TD
    A((A)) ---|3| B((B))
    A ---|1| C((C))
    C ---|2| B
    C ---|3| E((E))
    B ---|4| D((D))
    C ---|5| D
    E ---|6| D

이 그래프에서 신장 트리를 만드는 방법은 여럿입니다. 간선 일곱 개 가운데 사이클이 안 생기게 네 개를 고르면 모두 신장 트리입니다. 그중 합이 가장 작은 것을 찾는 것이 목표입니다.

가능한 신장 트리를 모두 늘어놓고 합을 비교하는 방법도 있습니다. 하지만 노드가 조금만 늘어도 신장 트리의 수가 너무 많아집니다. 그래서 큰 그래프에는 쓸 수 없습니다. 프림 알고리즘은 늘어놓지 않고 간선을 하나씩 골라 답에 닿습니다.

트리를 간선 하나씩 키우는 절차

A 를 출발점으로 두고 절차를 한 단계씩 따라갑니다. 절차는 노드를 두 쪽으로 나눠 봅니다. 이미 트리에 넣은 노드와 아직 트리 밖에 있는 노드입니다.

트리 밖 노드마다 값을 하나씩 적어 둡니다. 트리 안 노드와 바로 잇는 간선 가운데 가장 싼 것의 가중치입니다. 이 값을 흔히 키(key)라고 부릅니다. 그 간선이 트리의 어느 노드에 닿는지도 함께 적어 둡니다.

처음에는 출발점 A 의 키만 0 이고 나머지는 무한대입니다. 무한대는 트리에 바로 붙는 간선을 아직 못 찾았다는 표시입니다.

한 단계는 두 동작으로 이루어집니다.

1. 트리 밖 노드 가운데 키가 가장 작은 노드를 트리에 넣습니다. 그 키에 해당하는 간선도 트리에 넣습니다.
2. 방금 넣은 노드에 바로 붙은 트리 밖 이웃을 하나씩 봅니다. 새 노드와 잇는 간선이 지금 키보다 싸면 키를 그 가중치로 고칩니다.

아래 표는 예시 그래프에서 A 를 출발점으로 절차를 끝까지 돌린 것입니다. 표의 한 행이 한 단계입니다.

2단계에서 B 의 키가 3 에서 2 로 줄었습니다. A 에서 바로 오는 간선보다 C 에서 오는 간선이 싸기 때문입니다. 3단계에서는 D 의 키가 5 에서 4 로 줄었습니다.

4단계에서 E 를 넣은 뒤 E–D 간선의 가중치 6 을 봅니다. D 의 키 4 보다 크므로 고치지 않습니다. 트리 밖 노드가 남지 않으면 절차가 끝납니다.

결과는 간선 네 개, 가중치 합 10 입니다. 아래 그림은 같은 그래프에서 트리에 든 간선을 실선으로, 버린 간선을 점선으로 그린 것입니다.

flowchart TD
    A((A)) ---|1| C((C))
    C ---|2| B((B))
    C ---|3| E((E))
    B ---|4| D((D))
    A -.-|3| B
    C -.-|5| D
    E -.-|6| D

트리가 C 에서 두 갈래로 나뉩니다. 한 번 넣은 간선은 끝까지 빼지 않았습니다.

가장 싼 간선을 골라도 되는 까닭

매 단계에서 지금 가장 좋아 보이는 것을 고르고 되돌리지 않는 방식을 그리디 알고리즘이라고 합니다. 이런 방식은 대개 최적의 답을 놓칩니다. 프림 알고리즘이 놓치지 않는 까닭은 한 가지 성질에 있습니다.

바탕이 되는 성질은 컷 성질입니다. 먼저 컷부터 봅니다. 컷은 그래프의 노드를 두 쪽으로 가르는 것입니다. 프림 알고리즘의 매 단계가 이 컷입니다. 지금까지 키운 트리에 든 노드와 나머지 노드로 가르기 때문입니다.

이 절에서는 지금까지 키운 트리에 든 노드를 「고른 쪽」, 나머지 노드를 「남은 쪽」이라고 부릅니다. 매 단계에서 프림 알고리즘은 두 쪽을 가로지르는 간선 가운데 가장 싼 것을 고릅니다.

컷 성질은 이렇게 고른 간선이 답에서 벗어나지 않는다는 성질입니다. 두 쪽을 가로지르는 간선 가운데 가장 싼 것은 최소 신장 트리 가운데 적어도 하나에 들어 있습니다.

컷 성질이 맞는 까닭은 바꿔치기로 보입니다. 가로지르는 가장 싼 간선을 e 라고 부릅니다. e 가 안 든 최소 신장 트리 T 가 있다고 해 봅니다. T 는 프림이 키우는 트리와 다른, 비교하려고 따로 세운 트리입니다.

flowchart TD
    subgraph in["고른 쪽"]
        P((P))
        Q((Q))
    end
    subgraph out["남은 쪽"]
        R((R))
        S((S))
    end
    P ---|"e · 가로지르는 가장 싼 간선"| R
    Q ---|"f · T 에 든 가로지르는 간선"| S
    P -.-|"T 의 간선을 따라가는 길"| Q
    R -.-|"T 의 간선을 따라가는 길"| S

T 는 신장 트리라서 e 의 두 끝 P 와 R 도 T 의 간선을 따라 이어져 있습니다. P 는 고른 쪽에, R 은 남은 쪽에 있습니다. 그래서 그 길은 두 쪽을 가로지르는 간선을 적어도 하나 지납니다. 그 간선을 f 라고 부릅니다. f 의 두 끝은 그림처럼 Q 와 S 입니다.

T 에 e 를 더하면 이 길과 e 가 사이클을 이룹니다. 그 사이클에서 f 를 빼면 다시 사이클 없이 모두 이어진 트리가 됩니다.

e 는 가로지르는 간선 가운데 가장 싸므로 e 의 가중치는 f 이하입니다. 그래서 바꾼 트리의 합은 T 보다 크지 않습니다. T 가 이미 최소였으니 바꾼 트리도 최소 신장 트리입니다. 그 안에 e 가 들어 있습니다.

이 논리를 단계마다 이어 붙이면 됩니다. 앞에서는 T 를 e 가 안 든 최소 신장 트리로만 잡았습니다. 이번에는 T 를 지금까지 키운 트리를 통째로 품은 최소 신장 트리로 잡습니다. 바꿔치기 논리는 그대로 통합니다.

남은 물음은 f 를 빼도 지금 트리가 깨지지 않느냐입니다. f 는 두 쪽을 가로지릅니다. 지금 트리의 간선은 모두 고른 쪽 노드끼리만 잇습니다. 그래서 f 는 지금 트리의 간선이 아닙니다. f 를 빼도 지금 트리는 고스란히 남습니다.

곧 지금까지 키운 트리가 어떤 최소 신장 트리의 일부라면, 다음에 고른 간선을 더해도 여전히 어떤 최소 신장 트리의 일부입니다. 마지막 단계에서 모든 노드가 들어오면 그 트리가 곧 최소 신장 트리입니다.

이 논리는 가중치끼리 크기를 비교하기만 합니다. 가중치가 음수가 아니라는 조건을 어디에도 안 씁니다. 그래서 프림 알고리즘은 음수 가중치가 섞여도 맞는 답을 냅니다.

가중치가 모두 다르면 최소 신장 트리는 하나뿐입니다. 같은 가중치가 있으면 합이 같은 최소 신장 트리가 여럿일 수 있습니다. 앞의 예에서 A–B 와 C–E 는 둘 다 3 입니다. 그런데 A–B 는 넣는 순간 사이클이 생깁니다. 그래서 답이 하나로 정해졌습니다.

우선순위 큐로 다음 간선 고르기

매 단계의 첫 동작은 키가 가장 작은 노드를 고르는 일입니다. 그 고르기에 드는 비교 횟수를 줄이는 방법이 있습니다. 방법을 먼저 봅니다. 그다음 그 방법을 옮긴 파이썬 코드를 봅니다.

가장 단순한 방법은 키를 적은 표를 처음부터 끝까지 훑는 것입니다. 노드가 V 개면 한 번 고를 때마다 V 개를 비교합니다. 노드마다 한 번씩 고르므로 모두 합하면 V × V 번쯤 비교합니다.

비교 횟수를 줄이는 방법은 우선순위 큐를 쓰는 것입니다. 우선순위 큐는 넣어 둔 값 가운데 가장 작은 것을 먼저 꺼내 주는 자료구조입니다. 표를 훑는 대신 이 큐에서 하나를 꺼내면 다음에 붙일 간선이 나옵니다.

큐에는 노드가 아니라 간선을 넣습니다. 새 노드를 트리에 넣을 때마다 그 노드에서 트리 밖으로 나가는 간선을 모두 큐에 넣습니다. 그러면 한 노드로 들어가는 간선이 큐에 여럿 있을 수 있습니다. 꺼낸 간선의 끝이 이미 트리에 든 노드면 버리고 다음 것을 꺼냅니다.

우선순위 큐는 흔히 이진 힙으로 만듭니다. 이진 힙은 값을 나무 모양으로 매달아 가장 작은 값이 늘 맨 위에 오게 하는 구조입니다. 칸 하나 밑에 칸이 둘씩 달립니다. 그래서 한 층 내려갈 때마다 칸 수가 두 배로 늘어납니다.

값을 넣거나 꺼낼 때 전체를 다시 정리하지는 않습니다. 맨 위에서 맨 아래로 내려가는 한 갈래 길 위의 값만 자리를 바꿔 놓으면 됩니다.

그 길의 길이는 층의 수입니다. 층마다 칸 수가 두 배이므로 큐에 값이 n 개 있으면 층은 log n 개쯤입니다. log n 은 n 을 1 이 될 때까지 반으로 나눈 횟수입니다. 값이 백만 개여도 스무 번 남짓이라 매번 V 개를 훑는 것보다 훨씬 적습니다.

아래는 예시 그래프를 파이썬으로 옮긴 것입니다. 노드마다 (이웃, 가중치) 목록을 달아 두었습니다. 그래프를 이렇게 담는 방식을 인접 리스트라고 합니다.

graph = {
    "A": [("B", 3), ("C", 1)],
    "B": [("A", 3), ("C", 2), ("D", 4)],
    "C": [("A", 1), ("B", 2), ("D", 5), ("E", 3)],
    "D": [("B", 4), ("C", 5), ("E", 6)],
    "E": [("C", 3), ("D", 6)],
}

함수는 트리에 든 노드 모음 done, 우선순위 큐 pq, 고른 간선 목록 tree 셋을 씁니다. 큐에는 (가중치, 트리 쪽 노드, 트리 밖 노드) 묶음을 넣습니다. heapq 는 파이썬 리스트를 이진 힙으로 다루게 해 주는 표준 모듈입니다.

import heapq

def prim(graph, start):
    done = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    tree = []
    while pq and len(done) < len(graph):
        w, u, v = heapq.heappop(pq)
        if v in done:
            continue
        done.add(v)
        tree.append((u, v, w))
        for x, wx in graph[v]:
            if x not in done:
                heapq.heappush(pq, (wx, v, x))
    return tree

heappop 은 큐에서 가중치가 가장 작은 간선을 꺼냅니다. 그 간선의 끝 v 가 done 에 이미 있으면 건너뜁니다. 없으면 v 를 트리에 넣습니다. 그다음 v 에서 트리 밖으로 나가는 간선을 모두 큐에 넣습니다.

이 함수를 예시 그래프에 돌리면 간선 A–B 가 한 번 버려집니다. C–B 로 B 를 넣은 뒤에야 (3, A, B) 가 꺼내지기 때문입니다. 나머지는 앞 표의 순서와 같습니다.

tree = prim(graph, "A")
len(tree)                       # 4
sum(w for _, _, w in tree)      # 10
"".join(v for _, v, _ in tree)  # 'CBED'

간선 네 개를 골랐고 합은 10 입니다. 트리에 들어온 순서는 C, B, E, D 입니다.

걸리는 시간

그래프가 커질 때 걸리는 시간이 어떻게 늘어나는지를 노드 수와 간선 수로 따집니다. 노드 수를 V, 간선 수를 E 로 적습니다.

이런 늘어남은 빅오 표기법으로 적습니다. 빅오 표기법은 입력이 커질 때 비용이 어떤 모양으로 따라 커지는지를 적는 약속입니다. O(V²) 는 노드가 두 배가 되면 비용이 네 배쯤 된다는 뜻입니다.

다음 노드를 고르는 방법에 따라 걸리는 시간이 갈립니다.

힙 쪽의 시간은 큐를 다루는 횟수에서 나옵니다. 간선 하나는 큐에 많아야 한 번 들어갑니다. 꺼내는 횟수도 넣은 횟수를 넘지 않습니다. 그래서 넣기와 꺼내기가 모두 E 번 안쪽입니다. 한 번 넣거나 꺼낼 때마다 큐 크기의 log 만큼 걸립니다.

큐 크기는 E 까지 커질 수 있습니다. 그래서 한 번에 드는 시간은 log E 입니다. 간선 수는 노드 수의 제곱을 넘지 않습니다. E ≤ V² 이니 log E ≤ log V² = 2 log V 입니다. 빅오 표기법은 이런 상수 배를 떼므로 O(E log V) 로 적습니다.

간선이 노드 수의 제곱에 가까울 만큼 많으면 E log V 가 V² 보다 커집니다. 그런 그래프에서는 표를 훑는 쪽이 오히려 덜 걸립니다. 도로망처럼 한 노드에 이웃이 몇 개뿐인 그래프에서는 힙 쪽이 덜 걸립니다.

쓰는 메모리는 트리와 표에 V 만큼, 큐에 많아야 E 만큼입니다.

다익스트라 알고리즘과 다른 점

프림 알고리즘은 다익스트라 알고리즘과 뼈대가 같습니다. 다익스트라 알고리즘은 출발점 한 곳에서 다른 모든 곳까지 가장 짧은 길을 찾는 알고리즘입니다. 둘 다 우선순위 큐에서 가장 작은 것을 꺼내 한 노드씩 확정합니다.

갈리는 곳은 큐에 넣는 값 하나입니다. 프림은 트리에 바로 붙는 간선 하나의 가중치를 넣습니다. 다익스트라는 출발점부터 그 노드까지 지나온 간선의 가중치를 모두 더한 거리를 넣습니다.

그래서 만드는 트리도 다릅니다. 다익스트라가 만드는 것은 최단 경로 트리입니다. 출발점에서 각 노드로 가는 가장 짧은 길을 모은 트리입니다.

예시 그래프에서 D 를 보면 두 트리가 갈립니다.

프림은 D 를 붙일 간선으로 B–D(4) 와 C–D(5) 를 비교해 B–D 를 고릅니다. 다익스트라는 A 에서 D 까지의 거리를 비교합니다. B 를 거치면 1 + 2 + 4 로 7 입니다. C 에서 바로 가면 1 + 5 로 6 입니다. 그래서 C–D 를 고릅니다.

그래서 최소 신장 트리 위의 길이 가장 짧은 길은 아닙니다. 프림의 트리에서 A 에서 D 로 가면 7 이 걸리지만 가장 짧은 길은 6 입니다. 프림 알고리즘이 줄이는 것은 전체 가중치 합이지 두 노드 사이의 거리가 아닙니다.

크루스칼 알고리즘과 고르는 법

최소 신장 트리를 구하는 또 하나의 대표 절차가 크루스칼 알고리즘입니다. 크루스칼은 트리 하나를 키우지 않습니다. 간선 전체를 가중치 순으로 늘어놓고 싼 것부터 봅니다.

크루스칼은 간선을 넣어도 사이클이 안 생기면 넣습니다. 사이클이 생기면 버립니다. 처음에는 노드마다 따로 떨어진 조각입니다. 간선이 들어갈 때마다 조각이 합쳐집니다. 사이클 여부는 두 끝이 이미 같은 조각에 있는지로 가립니다.

이 물음에 빨리 답하려고 크루스칼은 서로소 집합이라는 자료구조를 씁니다. 원소가 어느 조각에 속하는지 묻는 일과 두 조각을 하나로 합치는 일을 빠르게 해 줍니다. 전체 시간은 간선을 정렬하는 데 드는 O(E log E) 가 좌우합니다.

그래프가 몇 조각으로 끊겨 있으면 신장 트리가 없습니다. 이때는 조각마다 최소 신장 트리를 구해 모은 최소 신장 숲을 답으로 삼습니다. 프림은 출발점이 있는 조각만 덮으면 멈춥니다. 그래서 남은 조각마다 다시 돌려야 합니다. 크루스칼은 한 번에 숲을 냅니다.

그래프를 담는 방식도 고르는 데 영향을 줍니다. 인접 행렬은 노드 수 × 노드 수 표의 칸마다 두 노드 사이 간선의 가중치를 적는 방식입니다. 한 노드의 이웃을 보려면 그 줄을 끝까지 훑어야 합니다. 그래서 키 표를 훑는 프림과 잘 맞습니다.

아래 표를 위에서부터 차례로 물어, 처음 맞는 줄의 절차를 고릅니다.

프림 알고리즘이 쓰이는 곳

모든 지점을 가장 싸게 잇는 문제에 바로 쓰입니다. 통신망 케이블, 전력선, 수도관처럼 여러 지점을 한 망으로 묶는 배선 설계가 그런 문제입니다. 지점이 노드, 놓을 수 있는 구간이 간선, 공사비가 가중치가 됩니다.

비슷한 것끼리 묶는 군집 분석에도 쓰입니다. 데이터 하나하나를 노드로, 두 데이터가 서로 다른 정도를 가중치로 둡니다. 최소 신장 트리에서 가중치가 가장 큰 간선을 몇 개 끊으면 트리가 여러 조각으로 나뉩니다. 그 조각 하나하나가 비슷한 것끼리의 묶음입니다.

관련 항목

프림 알고리즘이 속하는 상위 분류

알고리즘 · 그래프 알고리즘 · 그리디 알고리즘 · 최소 신장 트리

프림 알고리즘이 도는 그래프의 구성 요소

그래프 · 노드 · 간선 · 가중치 · 가중 그래프 · 무방향 그래프 · 연결 그래프 · 사이클 · 트리 · 신장 트리

최소 신장 트리 알고리즘이 쓰는 자료구조

우선순위 큐 · 힙 · 이진 힙 · 피보나치 힙 · 서로소 집합 · 인접 리스트 · 인접 행렬

같은 최소 신장 트리를 구하는 다른 알고리즘

크루스칼 알고리즘 · 보루프카 알고리즘 · 역삭제 알고리즘 · 최소 신장 숲

프림 알고리즘의 답을 보장하는 성질

컷 성질 · 사이클 성질 · 탐욕 선택 속성 · 최적 부분 구조

같은 뼈대로 그래프를 푸는 알고리즘

다익스트라 알고리즘 · 최단 경로 트리 · 너비 우선 탐색 · A 스타 알고리즘

최소 신장 트리로 푸는 문제

군집 분석 · 단일 연결 군집 · 외판원 순회 · 스타이너 트리 · 네트워크 설계

걸리는 시간을 적는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 로그 함수