6-6. 그래프: 최소 신장 트리 (MST - Prim, Kruskal)

1. 최소 신장 트리 (MST) 개요

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프 이론에서 매우 중요한 개념으로, 그래프 내의 모든 정점을 연결하면서 간선들의 가중치 합을 최소로 하는 트리 구조를 의미합니다. 여기서 "트리"는 사이클이 없는 연결된 그래프를 의미하며, "신장 트리"는 그래프의 모든 정점을 포함하는 트리를 뜻합니다. MST는 통신 네트워크 설계, 회로 설계, 클러스터링 등 다양한 실용적인 문제 해결에 활용됩니다. 핵심은 모든 노드를 연결하면서 최소 비용을 찾는 것입니다. 마치 여러 도시를 연결하는 도로망을 건설할 때, 모든 도시를 연결하면서 도로 건설 비용을 최소화하는 것과 유사합니다.

MST를 이해하기 위한 몇 가지 중요한 용어를 정리해 보겠습니다.

• 가중 그래프 (Weighted Graph): 각 간선에 가중치(비용, 거리 등)가 할당된 그래프입니다.
• 신장 트리 (Spanning Tree): 그래프의 모든 정점을 포함하는 트리입니다. 즉, 모든 정점을 연결하고 사이클이 없는 부분 그래프입니다.
• 최소 신장 트리 (Minimum Spanning Tree, MST): 신장 트리 중에서 간선 가중치의 합이 최소인 트리입니다.

2. MST 알고리즘: Prim과 Kruskal

MST를 찾는 알고리즘에는 여러 가지가 있지만, 가장 널리 사용되는 두 가지 알고리즘은 Prim 알고리즘과 Kruskal 알고리즘입니다. 이 두 알고리즘은 서로 다른 접근 방식을 사용하여 MST를 찾습니다.

1) Prim 알고리즘

Prim 알고리즘은 탐욕적인(Greedy) 방식으로 MST를 구축합니다. 임의의 정점에서 시작하여, 현재 MST에 포함된 정점과 MST에 포함되지 않은 정점 사이의 간선 중에서 가중치가 가장 작은 간선을 선택하여 MST를 확장해 나갑니다. 이러한 과정을 모든 정점이 MST에 포함될 때까지 반복합니다. Prim 알고리즘은 정점을 중심으로 MST를 구축해 나가는 방식이라고 이해할 수 있습니다.

2) Kruskal 알고리즘

Kruskal 알고리즘 역시 탐욕적인 알고리즘입니다. 하지만 Prim 알고리즘과는 다르게, 간선을 중심으로 MST를 구축합니다. 먼저, 그래프의 모든 간선을 가중치 순으로 정렬합니다. 그런 다음, 가중치가 작은 간선부터 차례대로 선택하면서 MST를 구성합니다. 단, 선택된 간선이 사이클을 형성하는 경우에는 해당 간선을 무시합니다. 모든 정점이 연결될 때까지 이 과정을 반복합니다.

3. Prim 알고리즘 상세 설명

Prim 알고리즘은 다음과 같은 단계로 진행됩니다.

1. 시작 정점 선택: 그래프의 임의의 정점을 시작 정점으로 선택합니다. 이 정점은 MST에 포함됩니다.
2. 가장 가까운 정점 찾기: MST에 포함된 정점과 MST에 포함되지 않은 정점 사이의 간선 중에서 가중치가 가장 작은 간선을 선택합니다. 이 간선으로 연결된 정점을 MST에 추가합니다.
3. 반복: 모든 정점이 MST에 포함될 때까지 2단계를 반복합니다.

Prim 알고리즘의 핵심은 매 단계마다 MST에 가장 가까운 정점을 선택한다는 것입니다. 이를 통해 지역적으로 최적의 선택을 반복하여 최종적으로 MST를 구성합니다.

Prim 알고리즘의 시간 복잡도는 인접 행렬을 사용하면 $O(V^2)$, 인접 리스트와 우선순위 큐(힙)를 사용하면 $O(E \log V)$입니다. 여기서 $V$는 정점의 수, $E$는 간선의 수입니다.

1) Prim 알고리즘의 예시

다음과 같은 가중 그래프를 예시로 Prim 알고리즘의 동작 과정을 살펴보겠습니다.

정점: A, B, C, D, E, F, G
간선:
  A-B: 2, A-C: 3, B-C: 4, B-D: 5, C-D: 1, C-E: 6, D-E: 7, D-F: 8, E-G: 9, F-G: 10

1. 시작 정점 A 선택: A를 MST에 추가합니다.
2. 가장 가까운 정점 찾기: A와 연결된 간선 중 가중치가 가장 작은 간선은 A-B (가중치 2)입니다. B를 MST에 추가합니다.
3. 다음 정점 선택: MST(A, B)에 연결된 간선 중 가장 가중치가 작은 간선은 A-C (가중치 3)입니다. C를 MST에 추가합니다.
4. 다음 정점 선택: MST(A, B, C)에 연결된 간선 중 가장 가중치가 작은 간선은 C-D (가중치 1)입니다. D를 MST에 추가합니다.
5. 다음 정점 선택: MST(A, B, C, D)에 연결된 간선 중 가장 가중치가 작은 간선은 C-E (가중치 6)입니다. E를 MST에 추가합니다.
6. 다음 정점 선택: MST(A, B, C, D, E)에 연결된 간선 중 가장 가중치가 작은 간선은 D-F (가중치 8)입니다. F를 MST에 추가합니다.
7. 다음 정점 선택: MST(A, B, C, D, E, F)에 연결된 간선 중 가장 가중치가 작은 간선은 E-G (가중치 9)입니다. G를 MST에 추가합니다.

최종 MST는 간선 A-B, A-C, C-D, C-E, D-F, E-G로 구성되며, 총 가중치는 2 + 3 + 1 + 6 + 8 + 9 = 29입니다.

4. Kruskal 알고리즘 상세 설명

Kruskal 알고리즘은 다음과 같은 단계로 진행됩니다.

1. 간선 정렬: 그래프의 모든 간선을 가중치 순으로 오름차순 정렬합니다.
2. 간선 선택 및 사이클 검사: 정렬된 간선을 순서대로 선택하면서, 해당 간선이 MST에 추가될 경우 사이클을 형성하는지 검사합니다.
3. MST 구성: 사이클을 형성하지 않는 간선을 MST에 추가합니다.
4. 반복: 모든 정점이 연결될 때까지 2, 3단계를 반복합니다.

Kruskal 알고리즘의 핵심은 사이클을 형성하지 않으면서 최소 가중치를 가진 간선을 선택하는 것입니다. 이를 위해 Union-Find 자료구조를 사용하여 사이클을 효율적으로 감지합니다.

Kruskal 알고리즘의 시간 복잡도는 간선 정렬에 $O(E \log E)$, Union-Find 연산에 $O(E \alpha(V))$입니다. 여기서 $E$는 간선의 수, $V$는 정점의 수, $\alpha$는 아커만 함수의 역함수이며, 거의 상수 시간으로 간주됩니다. 따라서 Kruskal 알고리즘의 전체 시간 복잡도는 $O(E \log E)$ 또는 $O(E \log V)$로 표현될 수 있습니다. (간선의 수를 정점의 제곱으로 표현 가능하다.)

1) Kruskal 알고리즘의 예시

위와 동일한 가중 그래프를 예시로 Kruskal 알고리즘의 동작 과정을 살펴보겠습니다.

정점: A, B, C, D, E, F, G
간선:
  A-B: 2, A-C: 3, B-C: 4, B-D: 5, C-D: 1, C-E: 6, D-E: 7, D-F: 8, E-G: 9, F-G: 10

1. 간선 정렬: 간선을 가중치 순으로 정렬합니다: C-D(1), A-B(2), A-C(3), B-C(4), B-D(5), C-E(6), D-E(7), D-F(8), E-G(9), F-G(10)
2. 간선 선택 및 사이클 검사:
   • C-D: MST에 추가 (사이클 없음)
   • A-B: MST에 추가 (사이클 없음)
   • A-C: MST에 추가 (사이클 없음)
   • B-C: 사이클 형성, 추가하지 않음
   • B-D: MST에 추가 (사이클 없음)
   • C-E: MST에 추가 (사이클 없음)
   • D-E: 사이클 형성, 추가하지 않음
   • D-F: MST에 추가 (사이클 없음)
   • E-G: MST에 추가 (사이클 없음)
   • F-G: 사이클 형성, 추가하지 않음
3. MST 구성 완료: 모든 정점이 연결되었으므로 MST 구성이 완료됩니다.

최종 MST는 간선 A-B, A-C, C-D, B-D, C-E, D-F, E-G로 구성되며, 총 가중치는 2 + 3 + 1 + 5 + 6 + 8 + 9 = 34입니다. Prim 알고리즘의 결과와 조금 다르지만, 이는 예시에서 주어진 간선들의 가중치가 서로 다르기 때문입니다. 이 예시에서는 Prim 알고리즘의 결과가 더 작은 값을 가집니다.

5. Prim vs Kruskal: 비교

Prim 알고리즘은 특정 정점에서 시작하여 MST를 확장해나가기 때문에, 특정 정점으로부터 MST를 구축해야 하는 경우에 유용합니다. 반면, Kruskal 알고리즘은 간선들을 가중치 순으로 정렬하여 MST를 구성하므로, 그래프 내의 모든 간선을 고려해야 하는 경우에 적합합니다.

6. MST 알고리즘의 활용

MST는 실생활과 다양한 분야에서 널리 활용됩니다.

• 통신 네트워크 설계: 여러 도시를 연결하는 통신 케이블을 설치할 때, 모든 도시를 연결하면서 케이블 설치 비용을 최소화하는 문제를 해결할 수 있습니다.
• 회로 설계: 전자 회로에서 부품 간의 연결을 설계할 때, 배선 길이를 최소화하여 회로의 효율성을 높일 수 있습니다.
• 클러스터링 (Clustering): 데이터 마이닝에서 데이터를 클러스터로 그룹화할 때, 서로 다른 데이터 포인트 간의 거리를 가중치로 간주하여 MST를 사용하여 클러스터를 형성할 수 있습니다.
• 이미지 처리: 이미지 분할(image segmentation)에 활용될 수 있으며, 픽셀 간의 유사성을 간선 가중치로 사용하여 이미지의 특징을 보존하면서 분할을 수행할 수 있습니다.
• 도로망 설계: 여러 도시를 연결하는 도로망을 설계할 때, 모든 도시를 연결하면서 도로 건설 비용을 최소화하는 문제를 해결할 수 있습니다.

7. 구현 (예시: Prim 알고리즘)

Prim 알고리즘을 C++로 구현한 예시입니다. (자세한 코드는 코드 블록으로 제공하지 않습니다.)

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // numeric_limits

using namespace std;

// 간선 정보를 저장하는 구조체
struct Edge {
  int to; // 연결된 정점
  int weight; // 가중치
};

// Prim 알고리즘 함수
int primMST(int startNode, const vector<vector<Edge>>& adj) {
  int numVertices = adj.size();
  vector<bool> visited(numVertices, false); // 방문 여부
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // <가중치, 정점>

  // 시작 정점 처리
  pq.push({0, startNode}); // 시작 노드는 가중치 0으로 시작
  int mstWeight = 0;

  while (!pq.empty()) {
    int weight = pq.top().first;
    int u = pq.top().second;
    pq.pop();

    if (visited[u]) continue; // 이미 방문한 정점이면 무시
    visited[u] = true;
    mstWeight += weight;

    for (const Edge& edge : adj[u]) {
      int v = edge.to;
      int w = edge.weight;
      if (!visited[v]) {
        pq.push({w, v}); // 우선순위 큐에 추가
      }
    }
  }

  // 모든 정점이 연결되었는지 확인
  for (bool v : visited) {
    if (!v) {
      return -1; // 연결되지 않은 정점이 있는 경우
    }
  }
  return mstWeight;
}

int main() {
  // 예시 그래프 (인접 리스트)
  int numVertices = 7;
  vector<vector<Edge>> adj(numVertices);

  // 간선 정보 추가 (가중치 있는 그래프)
  adj[0].push_back({1, 2});
  adj[0].push_back({2, 3});
  adj[1].push_back({0, 2});
  adj[1].push_back({2, 4});
  adj[1].push_back({3, 5});
  adj[2].push_back({0, 3});
  adj[2].push_back({1, 4});
  adj[2].push_back({3, 1});
  adj[3].push_back({1, 5});
  adj[3].push_back({2, 1});
  adj[4].push_back({1, 4});
  adj[5].push_back({3, 5});

  int startNode = 0; // 시작 정점
  int mstWeight = primMST(startNode, adj);

  if (mstWeight != -1) {
    cout << "MST 가중치: " << mstWeight << endl;
  } else {
    cout << "MST를 구성할 수 없습니다." << endl;
  }

  return 0;
}

위 코드는 Prim 알고리즘을 사용하여 그래프의 MST를 계산하는 간단한 예시입니다. 그래프는 인접 리스트로 표현되며, 우선순위 큐를 사용하여 최소 가중치를 가진 간선을 효율적으로 선택합니다. (주의: 코드는 완전한 구현체가 아니며, 이해를 돕기 위한 예시 코드입니다.)

8. 주의사항 및 트러블슈팅

• 그래프 표현 방식: 인접 행렬과 인접 리스트 중 적절한 그래프 표현 방식을 선택해야 합니다. 정점의 수와 간선의 수에 따라 시간 복잡도가 달라질 수 있습니다.
• 사이클 검사: Kruskal 알고리즘에서 사이클을 효율적으로 감지하기 위해 Union-Find 자료구조를 올바르게 구현해야 합니다. Union-Find의 효율성은 알고리즘 전체의 성능에 큰 영향을 미칩니다.
• 가중치의 음수 여부: MST 알고리즘은 일반적으로 음수 가중치를 처리하지 않습니다. 음수 가중치가 있는 그래프의 경우, 다른 알고리즘(예: Bellman-Ford)을 사용하거나 가중치를 양수로 변환해야 합니다.
• 연결되지 않은 그래프: 입력 그래프가 연결되어 있지 않은 경우, MST를 구성할 수 없습니다. Prim 알고리즘은 시작 정점에 따라 다른 MST를 생성할 수 있으며, Kruskal 알고리즘은 각 연결 요소를 MST로 구성합니다. (위 코드 예시에서는 MST를 구성할 수 없는 경우 -1을 반환하도록 처리)

9. 결론

최소 신장 트리(MST)는 그래프 이론에서 핵심적인 개념이며, Prim 알고리즘과 Kruskal 알고리즘은 MST를 찾는 대표적인 알고리즘입니다. 각 알고리즘의 원리와 특징을 이해하고, 문제 상황에 맞는 알고리즘을 선택하는 것이 중요합니다. MST는 다양한 실용적인 문제 해결에 활용될 수 있으며, 그 응용 범위는 끊임없이 확장되고 있습니다. 알고리즘의 동작 방식을 이해하고, 실제 문제에 적용하는 연습을 통해 MST에 대한 이해도를 높일 수 있습니다.