크루스칼 알고리즘

크루스칼 알고리즘은 여러 지점을 하나로 잇는 선들 가운데 비용 합이 가장 작은 묶음을 골라 줍니다. 먼저 모든 선을 싼 순서로 늘어놓습니다. 그리고 고리를 만들지 않는 선만 앞에서부터 집어 듭니다. 모든 지점이 한 덩어리로 이어지면 끝납니다.

쉽고 빠른 이해

마을 여러 곳을 광케이블로 모두 이을 때, 공사비 합이 가장 적게 드는 구간만 골라 줍니다. 마을 다섯 곳과 놓을 수 있는 구간 일곱 개, 구간마다의 공사비를 주면 놓을 구간 네 개가 나옵니다.

모든 마을이 서로 직접 이어질 필요는 없습니다. 다른 마을을 거쳐서라도 닿으면 됩니다. 놓는 방법을 전부 늘어놓고 비교하면 마을이 조금만 늘어도 가짓수가 감당 못 할 만큼 불어납니다.

모든 구간을 공사비가 싼 순서로 줄 세웁니다.
앞에서부터 하나씩 봅니다. 이미 다른 길로 이어진 두 마을 사이의 구간이면 버립니다. 아니면 놓습니다.
놓은 구간이 마을 수보다 하나 적어지면 멈춥니다.

대가는 둘입니다. 처음에 모든 구간을 한 번 줄 세워야 합니다. 구간이 많으면 이 줄 세우기가 시간을 거의 다 씁니다. 그리고 두 마을이 이미 이어졌는지를 매번 빨리 알아내는 장치가 따로 필요합니다.

마을마다 놓을 수 있는 구간이 몇 개뿐인 망에 잘 맞습니다. 거의 모든 마을 사이에 구간을 놓을 수 있는 망이면 프림이라는 다른 방법이 더 빨리 끝납니다.

상세

이 절은 크루스칼 알고리즘이 무엇을 받아 무엇을 내는지부터 봅니다. 그다음 노드 다섯 개짜리 작은 그래프 하나로 절차를 끝까지 따라갑니다. 답이 왜 맞는지, 두 노드가 이미 이어졌는지를 어떻게 빨리 묻는지, 얼마나 걸리는지는 그 뒤에 봅니다.

이름은 이 절차를 발표한 미국의 수학자 조지프 크루스칼(Joseph B. Kruskal)에게서 왔습니다.

넣는 것과 나오는 것

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

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

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

크루스칼 알고리즘이 받는 그래프의 간선에는 방향이 없습니다. 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

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

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

싼 간선부터 집어 드는 절차

절차는 간선을 가중치가 작은 순서로 한 번 정렬합니다. 그다음 앞에서부터 하나씩 보며 넣을지 버릴지를 정합니다. 이 절은 그 판단 기준을 먼저 세웁니다. 그다음 예시 그래프로 끝까지 돌려 봅니다.

판단에 쓰는 것은 조각입니다. 조각은 지금까지 넣은 간선으로 서로 이어진 노드의 묶음입니다. 처음에는 간선을 하나도 안 넣었으니 노드 하나가 조각 하나입니다.

간선 하나를 볼 때 묻는 것은 하나뿐입니다. 두 끝이 이미 같은 조각에 있느냐입니다. 같은 조각이면 두 끝은 이미 다른 길로 이어져 있습니다. 이 간선을 넣으면 사이클이 생기므로 버립니다.

두 끝이 다른 조각에 있으면 간선을 넣습니다. 그러면 두 조각이 하나로 합쳐집니다. 간선을 V − 1 개 넣으면 모든 노드가 한 조각이 되므로 거기서 멈춥니다.

그래프가 여러 덩어리로 끊겨 있으면 V − 1 개를 못 채운 채 간선이 바닥납니다. 그때 남은 조각마다 넣은 간선이 최소 신장 숲입니다.

아래 표는 예시 그래프에서 절차를 끝까지 돌린 것입니다. 표의 한 행이 간선 하나를 본 단계입니다. 마지막 칸은 그 단계가 끝난 뒤의 조각입니다.

단계	본 간선	두 끝의 조각	판단	단계 뒤의 조각
1	A–C · 1	다르다	넣음	{A, C} · {B} · {D} · {E}
2	C–B · 2	다르다	넣음	{A, B, C} · {D} · {E}
3	A–B · 3	같다	버림	{A, B, C} · {D} · {E}
4	C–E · 3	다르다	넣음	{A, B, C, E} · {D}
5	B–D · 4	다르다	넣음	{A, B, C, D, E}

3단계에서 A–B 를 버렸습니다. A 와 B 는 이미 A–C 와 C–B 를 거쳐 이어져 있기 때문입니다. 이 간선을 넣으면 A, C, B 를 도는 사이클이 생깁니다.

A–B 와 C–E 는 가중치가 둘 다 3 입니다. 가중치가 같은 간선끼리는 어느 것을 먼저 봐도 됩니다. 이 그래프에서는 C–E 를 먼저 봐도 A–B 가 버려지는 것은 같습니다.

5단계에서 간선이 네 개가 되어 멈췄습니다. C–D 와 E–D 는 보지도 않았습니다. 봤더라도 두 끝이 같은 조각이라 버려졌을 간선입니다.

결과는 간선 네 개, 가중치 합 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

싼 간선부터 넣어도 되는 까닭

매 단계에서 지금 가장 좋아 보이는 것을 고르고 되돌리지 않는 방식을 그리디 알고리즘이라고 합니다. 이런 방식은 대개 최적의 답을 놓칩니다. 크루스칼 알고리즘이 놓치지 않는 까닭은 두 성질에 있습니다. 하나는 버리는 간선을, 다른 하나는 넣는 간선을 받칩니다.

버리는 간선은 넣으면 사이클이 생기는 간선입니다. 그 사이클의 나머지 간선은 모두 앞 단계에서 넣은 것이라 가중치가 이 간선보다 크지 않습니다. 그래서 버리는 간선은 자기가 닫는 사이클에서 가장 비쌉니다.

사이클 성질은 이런 간선을 빼도 최소 합을 잃지 않는다는 성질입니다. 까닭은 간선 하나를 바꿔 넣어 보면 드러납니다.

사이클에서 가장 비싼 간선이 든 최소 신장 트리가 있다고 가정합니다. 그 간선을 빼면 트리가 두 쪽으로 갈립니다. 뺀 간선의 두 끝은 이제 서로 다른 쪽에 있습니다.

사이클의 나머지 간선은 뺀 간선의 두 끝을 잇는 다른 길입니다. 이 길은 한쪽에서 출발해 다른 쪽에서 끝납니다. 그러니 어딘가에서 두 쪽을 건너는 간선이 반드시 하나 있습니다.

그 간선은 뺀 간선보다 비싸지 않습니다. 그래서 대신 넣어도 합이 커지지 않습니다.

넣는 간선 쪽에는 컷이 필요합니다. 그래프의 노드를 두 쪽으로 가르는 것을 컷이라고 합니다. 조각 하나와 나머지 노드 전부로 가르는 것도 컷입니다.

한 끝은 이쪽, 다른 끝은 저쪽에 있는 간선을 컷을 가로지르는 간선이라고 부릅니다. 컷의 두 쪽을 이어 주는 간선은 이것들뿐입니다.

컷 성질은 가로지르는 간선 가운데 가장 싼 것이 어떤 최소 신장 트리에 들어 있다는 성질입니다. 그 간선이 안 든 최소 신장 트리가 있다고 가정합니다. 그 트리에 이 간선을 더하면 사이클이 생깁니다.

그 사이클은 더한 간선을 따라 컷을 한 번 건넙니다. 고리는 출발한 쪽으로 돌아와야 하므로 건너간 만큼 다시 건너와야 합니다. 그래서 사이클에는 컷을 가로지르는 간선이 하나 더 있습니다.

그 간선을 빼면 다시 사이클 없이 모두 이어진 트리가 됩니다. 뺀 간선은 더한 간선보다 싸지 않습니다. 그래서 바꾼 트리의 합은 원래보다 크지 않습니다. 바꾼 트리도 최소 신장 트리입니다.

크루스칼이 간선 e 를 넣는 순간에 이 성질을 적용합니다. e 의 한 끝이 속한 조각을 한쪽으로, 나머지 노드 전부를 다른 쪽으로 가르는 컷을 잡습니다. e 는 이 컷을 가로지릅니다.

아래 그림은 예시 그래프의 4단계, C–E 를 볼 때의 컷입니다. 위 칸이 C 가 든 조각이고 아래 칸이 나머지 노드입니다. 굵은 선이 e 인 C–E 입니다. 점선은 3단계에서 버린 A–B 입니다.

flowchart TD
    subgraph piece["e 의 한 끝이 든 조각"]
        A((A)) ---|1| C((C))
        C ---|2| B((B))
        A -.-|3| B
    end
    subgraph rest["나머지 노드"]
        E((E)) ---|6| D((D))
    end
    C ===|3| E
    B ---|4| D
    C ---|5| D

두 칸을 건너는 간선은 C–E · 3, B–D · 4, C–D · 5 셋입니다. 그 가운데 C–E 가 가장 쌉니다. 버린 A–B 는 A–C–B 사이클에서 가장 비싼 간선이었습니다. 이 간선은 위 칸 안에 갇혀 있습니다.

e 보다 싼 간선은 모두 앞에서 봤습니다. 넣은 간선은 조각 안의 두 노드를 잇습니다. 버린 간선도 같은 조각에 든 두 노드를 이었습니다.

조각은 합쳐지기만 하고 쪼개지지 않으므로 이 간선들은 지금도 한 조각 안에 있습니다. 그래서 어느 것도 이 컷을 가로지르지 않습니다. e 가 가로지르는 간선 가운데 가장 쌉니다.

한 단계만 맞아서는 부족합니다. 바꿔치기로 앞 단계에서 넣은 간선이 빠지면 앞의 결론이 무너집니다. 그래서 바꿔치기는 지금까지 넣은 간선을 모두 품은 최소 신장 트리에서 출발합니다.

그 트리에서 바꿔치기로 빼는 간선은 컷을 가로지르는 간선입니다. 지금까지 넣은 간선은 모두 어느 한 조각 안에 있어 컷을 가로지르지 않습니다. 그러니 바꿔치기로 빠지는 일이 없습니다.

그래서 단계마다 「지금까지 넣은 간선은 어떤 최소 신장 트리의 일부다」가 유지됩니다. 마지막에 모인 간선이 최소 신장 트리입니다.

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

가중치가 모두 다르면 최소 신장 트리는 하나뿐입니다. 같은 가중치가 있으면 합이 같은 최소 신장 트리가 여럿일 수 있습니다. 이때는 같은 가중치의 간선을 어느 순서로 보느냐에 따라 나오는 트리가 달라질 수 있습니다. 합은 늘 같습니다.

최소 신장 트리가 줄이는 것은 가중치 합입니다. 트리 위에서 두 노드 사이를 오가는 길이 가장 짧은 길은 아닙니다. 예시에서 트리를 따라 A 에서 D 로 가면 1 + 2 + 4 로 7 입니다. A–C–D 로 가면 1 + 5 로 6 입니다.

같은 조각인지 빨리 묻는 서로소 집합

절차에서 가장 자주 하는 일은 「두 끝이 같은 조각인가」를 묻는 것입니다. 간선마다 한 번씩 묻기 때문입니다. 이 절은 이 물음에 빨리 답하는 자료구조를 봅니다. 그다음 그 자료구조를 넣은 파이썬 코드로 예시 그래프를 돌려 봅니다.

가장 단순한 방법은 노드마다 조각 번호를 적은 표입니다. 묻기는 두 칸을 비교하면 끝납니다. 대신 두 조각을 합칠 때 한쪽 조각에 든 노드의 번호를 전부 고쳐야 합니다. 조각이 커지면 합치기 한 번이 오래 걸립니다.

이 두 일을 모두 빠르게 하는 자료구조가 서로소 집합입니다. 서로 겹치지 않는 묶음 여럿을 관리합니다. 원소가 어느 묶음에 드는지 찾는 일과 두 묶음을 합치는 일을 맡습니다. 두 일의 영어 이름을 따서 유니온 파인드(union-find)라고도 부릅니다. 크루스칼에서는 조각 하나가 묶음 하나입니다.

서로소 집합은 조각마다 노드를 나무 모양으로 매답니다. 노드마다 부모 하나만 기억합니다. 맨 위 노드는 부모가 자기 자신입니다. 이 노드를 그 조각의 대표라고 부릅니다.

찾기는 부모를 따라 맨 위까지 올라가 대표를 알아내는 일입니다. 두 노드의 대표가 같으면 같은 조각입니다. 합치기는 한쪽 대표를 다른 쪽 대표 밑에 매다는 일입니다. 대표 하나의 부모만 고치면 끝납니다.

이대로 두면 매달기가 쌓이면서 사슬이 길어질 수 있습니다. 사슬이 V 칸이면 찾기 한 번에 V 칸을 올라갑니다. 이를 막는 기법이 둘 있습니다.

첫째는 합칠 때 노드가 적은 조각을 많은 조각 밑에 매다는 것입니다. 어떤 노드가 한 칸 깊어질 때마다 그 노드가 든 조각은 두 배 이상으로 커집니다.

까닭은 이렇습니다. 노드가 깊어지는 것은 자기 조각이 적은 쪽이 되어 다른 조각 밑에 매달릴 때뿐입니다. 상대 조각은 자기 조각보다 크거나 같습니다. 그러니 합친 조각은 자기 조각의 두 배 이상입니다.

아래 그림은 노드가 한 개씩인 조각에서 시작해 두 번 합친 모습입니다. 위에 있는 노드가 부모입니다.

flowchart TD
    subgraph one["노드 1 개 + 1 개 → 2 개"]
        P1((P)) --- Q1((Q))
    end
    subgraph two["노드 2 개 + 2 개 → 4 개"]
        P2((P)) --- Q2((Q))
        P2 --- R2((R))
        R2 --- S2((S))
    end
    Q1 ~~~ P2

첫 합치기에서 Q 가 P 밑에 매달려 한 칸 깊어졌습니다. 조각은 노드 2 개가 됐습니다. 둘째 합치기에서는 R 을 대표로 S 가 붙은 조각이 P 밑에 매달렸습니다. S 는 두 칸 깊이가 됐습니다. 조각은 노드 4 개가 됐습니다.

log V 는 V 를 1 이 될 때까지 반으로 나눈 횟수입니다. 조각은 V 를 넘을 수 없으니 두 배로 커지는 일은 많아야 log V 번 일어납니다. 그래서 어느 노드의 깊이도 log V 를 넘지 않습니다.

둘째는 경로 압축입니다. 찾기를 하면서 지나간 노드를 모두 대표 밑에 바로 매답니다. 다음번에 그 노드들을 찾으면 한 칸만 올라가면 됩니다.

아래 그림은 한 조각에서 Z 를 찾기 전과 뒤입니다. 위에 있는 노드가 부모이고 W 가 대표입니다.

flowchart TD
    subgraph before["Z 를 찾기 전"]
        W1((W)) --- X1((X))
        X1 --- Y1((Y))
        Y1 --- Z1((Z))
    end
    subgraph after["Z 를 찾은 뒤"]
        W2((W)) --- X2((X))
        W2 --- Y2((Y))
        W2 --- Z2((Z))
    end
    Z1 ~~~ W2

찾기 전에는 Z 에서 W 까지 세 칸을 올라갑니다. 찾은 뒤에는 Z 와 그 길에 있던 Y 가 W 에 바로 붙어 한 칸이면 됩니다.

두 기법을 함께 쓰면 찾기와 합치기 한 번에 드는 시간이 사실상 상수가 됩니다. 이론으로는 아커만 역함수라는 아주 느리게 자라는 함수만큼 걸립니다. 이 함수의 값은 현실에서 다룰 수 있는 어떤 V 에서도 4 를 넘지 않습니다.

아래는 예시 그래프의 간선 목록을 파이썬으로 옮긴 것입니다. 간선마다 가중치, 한 끝, 다른 끝 순서로 적었습니다. 가중치를 맨 앞에 두면 목록을 정렬할 때 가중치 순서로 늘어섭니다.

Python

edges = [
    (3, "A", "B"), (1, "A", "C"), (2, "C", "B"),
    (3, "C", "E"), (4, "B", "D"), (5, "C", "D"),
    (6, "E", "D"),
]

함수는 부모를 적은 parent, 대표마다 조각의 노드 수를 적은 size, 고른 간선 목록 tree 셋을 씁니다. find 가 찾기와 경로 압축을 함께 합니다. 반복문 안의 네 줄이 노드가 적은 조각을 많은 조각 밑에 매다는 합치기입니다.

Python

def kruskal(nodes, edges):
    parent = {v: v for v in nodes}
    size = {v: 1 for v in nodes}

    def find(v):
        if parent[v] != v:
            parent[v] = find(parent[v])
        return parent[v]

    tree = []
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        if size[ru] < size[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]
        tree.append((u, v, w))
        if len(tree) == len(nodes) - 1:
            break
    return tree

sorted(edges) 가 간선을 가중치 순으로 늘어놓습니다. 두 끝의 대표 ru 와 rv 가 같으면 continue 로 버립니다. 다르면 합치고 간선을 tree 에 넣습니다. 간선이 노드 수보다 하나 적어지면 break 로 멈춥니다.

이 함수를 예시 그래프에 돌리면 앞 표와 같은 순서로 간선을 고릅니다.

Python

tree = kruskal("ABCDE", edges)
len(tree)                    # 4
sum(w for _, _, w in tree)   # 10
picked = [u + v for u, v, _ in tree]
picked  # ['AC', 'CB', 'CE', 'BD']

간선 네 개를 골랐습니다. 합은 10 입니다. 고른 순서는 A–C, C–B, C–E, B–D 입니다.

걸리는 시간

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

이런 늘어남은 빅오 표기법으로 적습니다. 빅오 표기법은 입력이 커질 때 비용이 어떤 모양으로 따라 커지는지를 적는 약속입니다. O(E log E) 는 비용이 E 에 log E 를 곱한 모양으로 커진다는 뜻입니다.

크루스칼 알고리즘의 시간은 두 부분으로 나뉩니다. 처음에 간선을 정렬하는 데 O(E log E) 가 듭니다. 그 뒤 간선마다 찾기를 두 번 하고 합치기를 많아야 V − 1 번 합니다.

서로소 집합의 두 기법을 모두 쓰면 뒤 부분은 E 에 거의 비례합니다. 그래서 전체 시간은 정렬이 정합니다. O(E log E) 입니다.

같은 시간을 O(E log V) 로 적기도 합니다. 간선 수는 노드 수의 제곱을 넘지 않습니다. E ≤ V² 이니 log E ≤ log V² = 2 log V 입니다. 빅오 표기법은 이런 상수 배를 떼므로 둘은 같은 크기입니다.

조각을 관리하는 방법에 따라 뒤 부분이 달라집니다. 아래 표는 정렬을 뺀 뒤 부분과 정렬을 넣은 전체를 나눠 적은 것입니다.

조각을 관리하는 방법	찾기 한 번	정렬을 뺀 뒤 부분	정렬을 넣은 전체
부모만 따라 올라가기	O(V)	O(E × V)	O(E × V)
적은 조각을 많은 조각 밑에	O(log V)	O(E log V)	O(E log E)
위 방법 + 경로 압축	사실상 상수	E 에 거의 비례	O(E log E)

둘째 행과 셋째 행은 전체가 같습니다. 둘 다 정렬이 전체 시간을 정하기 때문입니다. 경로 압축이 줄이는 것은 뒤 부분입니다.

간선이 이미 가중치 순으로 정렬되어 들어오면 정렬하는 부분이 사라집니다. 그러면 전체가 E 에 거의 비례합니다. 가중치가 작은 정수라면 비교 없이 개수를 세어 정렬하는 계수 정렬로 정렬도 E 에 비례하게 할 수 있습니다.

쓰는 메모리는 간선 목록에 E 만큼, parent 와 size 에 V 만큼입니다.

프림 알고리즘과 고르는 법

최소 신장 트리를 구하는 또 하나의 대표 절차가 프림 알고리즘입니다. 프림은 출발 노드 하나에서 트리 하나를 키웁니다. 매 단계 지금 트리에 바로 붙는 간선 가운데 가장 싼 것을 더합니다.

프림은 다음 간선을 고를 때 우선순위 큐를 씁니다. 우선순위 큐는 넣어 둔 값 가운데 가장 작은 것을 먼저 꺼내 주는 자료구조입니다. 크루스칼이 정렬과 서로소 집합으로 하는 일을 프림은 이 큐 하나로 합니다.

그래프를 담는 방식도 둘을 가릅니다. 인접 리스트는 노드마다 이웃과 그 간선의 가중치를 목록으로 달아 두는 방식입니다. 한 노드에서 뻗은 간선을 바로 꺼낼 수 있습니다.

인접 행렬은 노드 수 × 노드 수 표의 칸마다 두 노드 사이 간선의 가중치를 적는 방식입니다. 두 노드 사이에 간선이 있는지를 칸 하나로 바로 알 수 있습니다.

프림은 매 단계 방금 트리에 붙은 노드의 이웃을 꺼냅니다. 그래서 노드에서 이웃을 찾는 이 두 방식과 잘 맞습니다. 크루스칼은 간선을 한 줄로 늘어놓고 정렬하므로 간선 리스트가 편합니다.

인접 행렬로 받은 프림은 우선순위 큐 없이도 돕니다. 노드마다 지금 트리까지 가장 싼 간선의 가중치를 적어 둡니다. 매 단계 노드 V 개를 한 번씩 훑어 가장 싼 노드를 고릅니다. 이 훑기를 V 번 하므로 O(V²) 입니다.

두 알고리즘이 내는 트리의 가중치 합은 같습니다. 갈리는 것은 답을 키우는 방식입니다.

	크루스칼 알고리즘	프림 알고리즘
답을 키우는 방식	흩어진 조각을 합친다	트리 하나를 키운다
다음 간선을 고르는 범위	정렬한 간선 전체	지금 트리에 바로 붙는 간선
쓰는 자료구조	서로소 집합	우선순위 큐
잘 맞는 입력	간선 리스트	인접 리스트 · 인접 행렬
출발 노드	필요 없다	하나 고른다
끊긴 그래프	한 번에 최소 신장 숲	출발 노드의 덩어리만 덮는다
걸리는 시간	O(E log E)	우선순위 큐로 O(E log V) · 행렬을 훑으면 O(V²)

간선이 노드 수의 제곱에 가까울 만큼 많으면 정렬할 간선이 그만큼 많아집니다. 그런 그래프에서는 행렬을 훑는 프림의 O(V²) 가 덜 걸립니다.

도로망처럼 한 노드에 이웃이 몇 개뿐인 그래프는 간선 수가 노드 수와 비슷합니다. 그만큼 정렬할 간선도 적습니다.

그래서 간선이 드문 그래프나 간선 리스트로 받은 입력에는 크루스칼을 고릅니다. 간선이 빽빽한 그래프에는 프림을 고릅니다.