최소 신장 트리 (MST)

🧩 MST란?

MST(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프에서 선택한 간선들의 가중치 합이 최소가 되도록 하는 트리다.

 

위 말을 쉽게 풀어서 쓰자면 "모든 장소를 연결하되 비용이 가장 적게 드는 연결 방법"이다.

마을에 도로를 만든다면?

A, B, C, D 마을 사이를 잇는 도로의 공사비가 다음과 같다고 하자.

일반적인 공사 담당자라면 네 마을 중 어디서 출발해도 서로 갈 수 있게 도로를 만들되, 도로 공사비는 최대한 적게 쓰고 싶을 것이다.

 

우선 모든 도로를 다 만들면 비용은 15억이 된다. 하지만 A-B, B-C, C-D 도로만 만들면 6억만 쓰면 된다. 이렇게 모든 마을을 연결하면서 비용은 최소인 도로 선택이 바로 MST다.

 

MST(A-B-C-D)에서는 A-B-C-A로 이어지는 사이클이 생성되지 않는다. A에서 B로 갈 수 있고, B에서 C로 갈 수 있는데 굳이 A와 C를 잇는 비싼 도로를 또 지을 필요는 없다.

MST의 조건 세 가지

1. 모든 장소가 연결되어야 함
2. 불필요한 연결(사이클)이 없어야 함
3. 총 비용이 최소여야 함

왜 간선 수가 "정점 수 - 1"인가?

위의 예시에서 보았듯이 마을이 4개라면 최소한 선 3개가 있어야 모두 연결할 수 있다. 즉 정점 수가 V개라면 MST의 간선 수는 V-1개가 된다.

언제 MST를 써야 할까?

알고리즘 문제를 풀다가 다음과 같은 표현이 나온다면 MST를 고려해 볼 수 있다.

• 모든 섬을 다리로 연결해라
• 모든 마을에 전기를 공급해라
• 연결 비용의 합을 최소로 해라
• 도로 건설 비용을 최소로 해라

🧩 Kruskal 알고리즘

Kruskal은 가장 가중치가 적은 간선부터 고르되 사이클이 생기는 간선은 버리는 방식이다.

이번에는 네 마을을 잇는 도로가 다음과 같이 구성되어 있다고 가정해 보자.

Kruskal 진행 과정

1. 도로를 비용 순으로 정렬한다.

A - B : 1
A - D : 2
C - D : 3
A - C : 4
B - D : 5

2. 가장 싼 A - B를 선택한다. (비용 합 = 1)

3. 그 다음으로 싼 A - D를 선택한다. (비용 합 = 3) → 사이클이 생성되지 않았으므로 선택한다.

4. 그 다음으로 싼 C - D를 선택한다.(비용 합 = 6) → 사이클이 생성되지 않았으므로 선택한다.

5. 마을 4개가 전부 연결되었고 도로도 3개이므로 종료한다.

사이클 생성 판단: Union-Find

Kruskal에서는 사이클이 생성되는지 확인하기 위해 Union-Find를 사용한다.

 

위에서 3단계까지 진행했다고 가정했을 때, 네 마을은 두 개의 그룹으로 나뉜다.

• 그룹 1: A, B, D
• 그룹 2: C

여기서 B - D를 선택한다고 하자. B와 D는 같은 그룹에 속해 있다. 즉 이미 연결되어 있기 때문에 도로를 추가하면 사이클이 발생하게 된다. 이렇게 같은 그룹인지 확인하고, 서로 다른 그룹이면 합치는 기능을 Union-Find라고 한다.

• find(x): x가 속한 그룹 찾기
• union(a, b): a 그룹과 b 그룹 합치기

🧩 Prim 알고리즘

Prim은 하나의 노드에서 출발해서 현재 연결된 노드들과 이어지는 가장 가중치가 적은 간선을 계속 고르는 방식이다.

 

Kruskal이 그래프 전체에서 싼 도로를 찾는 방식이라면, Prim은 현재 만들어진 마을 영역을 점점 넓히는 방식이다.

Prim 진행 과정

1. 시작 마을로 A 선택

[A]    B    C    D

A - B : 1
A - D : 2
A - C : 4

2. A - B 선택

[A] -- 1 -- [B]

C    D

/* A 또는 B에서 아직 연결되지 않은 도시 */
A - D : 2
A - C : 4
B - D : 5

3. A - D 선택

    [B]
     |
     1
     |
    [A]
     |
     2
     |
    [D]

[C]

D - C : 3
A - C : 4

4.  D - C 선택

[B]
 |
1
 |
[A]
 |
2
 |
[D]
 |
3
 |
[C]

5. 모든 도시가 연결되었으므로 종료한다.

🧩 Kruskal vs Prim

구분	Kruskal	Prim
시작 방식	모든 도로를 비용순으로 봄	특정 도시 하나에서 시작
선택 기준	그래프 전체에서 가장 싼 도로	현재 연결된 영역 밖으로 나가는 가장 싼 도로
사이클 처리	Union-Find로 확인	방문한 도시를 다시 추가하지 않음
주 자료구조	간선 리스트 + Union-Find	인접 리스트 + 우선순위 큐
이미지	여러 조각을 합치는 방식	한 덩어리를 키우는 방식

• Kruskal은 작은 연결 조각들을 점점 합쳐 나가는 방식

A B C D E
A-B C-D E
B-B-C-D E

• Prim은 A에서 시작해서 연결된 영역을 키우는 방식

A
A-B
A-B-D
A-B-D-C

알고리즘 선택 기준

• Kruskal이 적합한 경우
  • 입력이 간선 형태인 경우
  • 간선 정렬이 편한 경우
  • 그래프가 비교적 희소한 경우
  • Union-Find를 활용해야 하는 경우
• Prim이 적합한 경우
  • 인접 리스트 형태로 그래프를 구성한 경우
  • 특정 정점에서 확장하는 방식이 자연스러운 경우
  • 우선순위 큐를 활용해야 하는 경우

Java 코드 예시

• Kruskal

// 모든 간선을 비용순 정렬
Collections.sort(edges);

// 싼 간선부터 확인
for (Edge edge : edges) {

    // 두 도시가 아직 연결되지 않았다면 선택
    if (union(edge.from, edge.to)) {
        totalCost += edge.weight;
        selectedEdges++;
    }
}

• Prim

// 가장 비용이 작은 도로를 먼저 꺼내기 위한 큐
PriorityQueue<Edge> pq = new PriorityQueue<>();

// 시작점 1번 도시
pq.offer(new Edge(1, 0));

while (!pq.isEmpty()) {
    Edge current = pq.poll();

    // 이미 연결된 도시라면 건너뜀
    if (visited[current.to]) {
        continue;
    }

    visited[current.to] = true;
    totalCost += current.weight;

    // 새로 연결된 도시에서 갈 수 있는 도로 추가
    for (Edge next : graph[current.to]) {
        if (!visited[next.to]) {
            pq.offer(next);
        }
    }
}