[알고리즘] 최소 신장 트리(MST) - 크루스칼 알고리즘과 프림 알고리즘

이 글에서는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 대표적인 알고리즘인 크루스칼 알고리즘과 프림 알고리즘에 대해 정리하였습니다.

---

최소 신장 트리(Minimum Spanning Tree, MST)

MST의 개념

• 가중치가 있는 무방향 그래프에서, 모든 정점을 연결하면서 그 간선들의 가중치 합이 최소가 되는 서브그래프를 의미
• 조건 : 모든 정점을 포함 + 사이클이 없는 트리 구조 + 간선 가중치의 합이 최소

MST를 구하는 대표 알고리즘

크루스칼(Kruskal) 알고리즘

• 간선을 가중치 오름차순으로 정렬한 뒤, 가장 작은 것부터 하나씩 트리에 포함시킬지 결정
• 이미 사이클이 형성되는 간선은 버리고, 아니면 포함
• 사이클 판별을 빠르게 하기 위해 Union Find(서로소 집합, DSU)를 사용

Union Find 참고자료) [자료구조] 서로소 집합 자료구조 (Disjoint Set Union, DSU) - Union Find

[자료구조] 서로소 집합 자료구조 (Disjoint Set Union, DSU) - Union Find

프림(Prim) 알고리즘

• 임의 정점에서 시작해, 방문하지 않은 정점 중 가장 싼 간선을 골라 확장해 나가는 방식(그래프 탐색 형식)
• Union Find가 필수적으로 사용되지 않음

일반적으로 Kuskal + Union Find 조합이 간단하고 직관적이며, 간선 중심 접근이 편리해 자주 사용된다.

---

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘의 개념

핵심 아이디어

• 간선들을 가중치 기준 오름차순 정렬
• 가장 작은 가중치 간선부터 차례대로 수행
  • 지금 이 간선을 추가하면 사이클이 형성되는가?
    • 사이클이 생기면 제외 (스킵)
    • 사이클이 생기지 않으면 채택 (MST에 포함)
• (정점이 N개일 때) 간선이 N-1개 선택되면 MST 완성

특징

• 사이클 판별에 Union Find (DSU) 자료구조를 사용하여 두 정점이 이미 같은 연결 요소에 속하는지 빠르게 검사 가능
• 간선 정렬은 $ O(E \log E) $, Union Find 연산은 최적화시 거의 $ O(E) $ 이므로, 전체 $ O(E \log E) $ 시간 복잡도로 수행 가능

크루스칼 알고리즘 구현

1. 간선 입력 : (start, end, weight) 형태로 mst 배열에 저장
2. 정렬 수행
3. Union Find 초기화 : 모든 노드에 대해 parent[i] = i로 초기화
4. 오름차순 간선을 하나씩 Union Find를 수행하며 반복

/*
입력 예시
5 7
0 1 7
0 2 23
0 4 3
1 2 5
1 3 21
1 4 12
3 4 2
*/

#include <algorithm>
#include <iostream>
using namespace std;

struct NODE {
  // 출발 노드, 도착 노드, 가중치
  int start;
  int end;
  int weight;
  bool operator<(struct NODE right) {
    // 가중치 기준으로 오름차순 정렬
    if (weight < right.weight) return true;
    if (weight > right.weight) return false;

    // 가중치가 같을 때 출발 노드 기준으로 오름차순 정렬
    if (start < right.start) return true;
    if (start > right.start) return false;

    // 출발 노드도 같으면, 도착 노드 기준으로 정렬
    if (end < right.end) return true;
    if (end > right.end) return false;

    return false;
  }
};

// 대표 노드 체크를 위한 DAT
int parent[10];       // index : 노드 번호 / value : 대표 노드 번호
struct NODE mst[10];  // 노드 정보 담을 구조체 배열

// Find 특정 그룹의 대표 찾기 ( 재귀 )
int Find(int n) {
  // 대표가 본인인 경우 return
  if (n == parent[n]) return n;
  // root 노드까지 찾아가기 - 경로 압축
  return parent[n] = Find(parent[n]);
}

// Union 그룹을 합친다.
void Union(int A, int B) {
  // 그룹을 합칠 때, 같은 그룹인지 체크해야 한다.
  int rootA = Find(A);
  int rootB = Find(B);
  // 같은 그룹이라면 종료
  if (rootA == rootB) return;
  // 대표 정보 업데이트
  parent[rootB] = rootA;
}

int main() {
  int N, M;
  cin >> N >> M;
  // 1. 데이터 저장
  for (int i = 0; i < M; i++) {
    int s, e, w;
    cin >> s >> e >> w;
    mst[i] = {s, e, w};
  }

  // 2. weight 기준 오름차순 정렬
  sort(mst, mst + M);

  // parent 세팅 ( Union-Find )
  for (int i = 1; i <= N; i++) {
    // 본인이 대표
    parent[i] = i;
  }

  // MST의 최소값 저장할 변수
  int sum = 0;
  // 3. 하나씩 연결하기
  // 맨 앞에 간선의 가중치가 최소부터 시작
  for (int i = 0; i < M; i++) {
    struct NODE now = mst[i];
    // 같은 그룹인 경우 무시
    if (Find(now.start) == Find(now.end)) continue;
    // 다른 그룹이면 합치기
    Union(now.start, now.end);
    // 가중치 누적
    sum += now.weight;
  }

  // 합계 출력
  cout << sum << '\n';

  return 0;
}

크루스칼 알고리즘의 시간 복잡도

• 간선 정렬 : E개의 간선에 대해 $ O(E \log E) $
• Union Find 초기화 : V개의 노드에 대해 $ O(V) $
• 간선 순회 : E번 반복, 각 반복에서 Find 2회, Union 1번 수행 > 경로 압축 및 랭크 최적화시 거의 $ O(1) $
• 총합 : $ O(E \log E) $ (정렬이 지배)

---

프림(Prim) 알고리즘

프림 알고리즘의 개념

정의

• MST 알고리즘의 하나로, 임의의 한 정점에서 시작하여, 방문하지 않은 정점 중 현재 MST와 연결되는 간선 중 가장 비용이 작은 간선을 선택하여 트리를 확장해 나가는 방식

핵심 아이디어

• 한 정점에서 시작해, 방문하지 않은 정점 중 MST에 추가할 간선을 가장 적은 비용으로 골라가며 확장 

동작 흐름 (간단 예시)

• MST에 아무 정점이나 하나 선택해 시작 (방문 처리)
• 현재 MST와 연결된 모든 간선 중, 가장 가중치가 작은 간선을 찾아 방문하지 않은 정점을 MST에 포함
• 새로 방문한 정점과 연결된 간선들을 후보에 추가
• 이를 N-1개의 간선을 얻을 때까지(혹은 모든 정점을 방문할 때까지) 반복

프림 알고리즘의 구현 방식

인접 행렬 기반 구현

• 인접 행렬로 그래프가 주어졌다고 가정하면, 방문하지 않은 정점 중 MST에 연결되는 간선 중 최소 가중치를 찾기 위해 $ O(V) $ 탐색 필요
• 전체 V개 정점을 MST에 넣으므로 $ O(V^2) $

인접 리스트 기반 구현

• 인접 리스트와 우선순위 큐를 사용하면 $ O(E \log V) $ 정도로 구현 가능
• 주로 인접리스트 + 우선순위 큐(최소힙) 방식을 사용하면 대규모 그래프에서 효율적으로 동작

프림 알고리즘 구현

#include <iosteram>
#include <queue>
#include <vector>

using namespace std;

struct Edge {
  int to;
  int w;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, M;  // 정점 수 N, 간선 수 M
  cin >> N >> M;

  vector<vector<Edge>> graph(N + 1);
  for (int i = 0; i < M; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    // 무방향 그래프
    graph[a].push_back({b, w});
    graph[b].push_back({a, w});
  }

  // Prim's Algorithm - 인덱스 방식
  // 1. 임의의 시작 정점(보통 1번)
  int start = 1;
  long long mst_cost = 0;  // MST 총 비용
  vector<bool> visited(N + 1, false);

  // 우선순위 큐: (간선비용, 연결정점)
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      pq;

  // 시작점 (cost=0)으로 삽입
  pq.push({0, start});
  int cnt = 0;  // MST에 포함된 정점 수

  while (!pq.empty()) {
    auto [cost, u] = pq.top();
    pq.pop();

    if (visited[u]) continue;
    visited[u] = true;
    mst_cost += cost;
    cnt++;

    // u의 인접 간선을 큐에 넣기
    for (int i = 0; i < (int)graph[u].size(); i++) {
      int v = graph[u][i].to;
      int w = graph[u][i].w;
      if (!visited[v]) {
        pq.push({w, v});
      }
    }
  }

  // MST에 포함된 정점 수 cnt가 N이면 전체 연결
  // (그렇지 않다면 연결되지 않은 그래프)

  cout << mst_cost << "\n";
  return 0;
}

프림 알고리즘의 시간 복잡도

• 우선순위 큐 사용시, 각 정점이 1번씩 MST에 들어가며, 각 간선이 최대 1 ~ 2회 정도 push / pop 될 수 있음
• 일반적으로 $ O(E \log V) $의 시간복잡도를 가짐
• 인접 행렬 + 선형 탐색 방식을 사용하면 $ O(V^2) $의 시간 복잡도를 가짐