최소 신장 트리 (MST)

최소 신장 트리 (MST)란?

가중치가 있는 무방향 그래프에서 모든 정점이 연결되고, 간선의 가중치 합이 최소가 되는 트리
신장 트리는 주어진 그래프의 모든 정점을 포함하며, 사이클이 없는 트리

MST의 특징

1. 간선의 개수는 항상 $V - 1$ ($V$는 정점의 개수)
2. 최소 비용으로 연결: 모든 정점을 연결할 수 있는 최소한의 간선을 포함
3. 유일한 해가 아닐 수 있음: 동일한 최소 비용을 가지는 여러 개의 MST가 존재할 수 있음

장점

1. 최적의 해를 보장: MST 알고리즘은 항상 최소 비용의 신장 트리를 구할 수 있음
2. 네트워크 연결, 군집화 등 다양한 문제에 적용 가능.

단점

1. 가중치가 음수인 경우에는 적용할 수 없습니다.
2. Dense 그래프에서 비효율적일 수 있음. 특히 간선이 많은 경우 프림 알고리즘은 우선순위 큐를 사용할 때 비효율적일 수 있음

MST의 활용

• 네트워크 연결 비용 최소화: 최소한의 비용으로 모든 노드를 연결할 때
• 도로 건설 비용 최소화: 도시 간 도로 연결 시 최소한의 비용을 찾을 때
• 클러스터링 문제: 데이터 군집을 생성할 때 MST를 이용하여 데이터 간 연결을 최소화

MST 알고리즘의 종류

대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal’s Algorithm) 과 프림 알고리즘(Prim’s Algorithm)
두 알고리즘은 서로 다른 접근 방식을 사용하지만, 모두 최적의 MST를 구할 수 있음

크루스칼 알고리즘 (Kruskal’s Algorithm)

그리디 알고리즘을 사용하여, 간선을 가중치 오름차순으로 정렬하고, 사이클이 발생하지 않는 간선을 차례로 선택하여 MST를 구성하는 방식
주로 Union-Find 자료구조를 사용하여 사이클 여부를 판별

시간 복잡도
간선 정렬: O(E log E) (E는 간선의 개수)
Union-Find: O(E * α(V)) (α(V)는 역 아커만 함수, 매우 작은 값)
전체 시간 복잡도: O(E log E)

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;  // 가중치 기준으로 정렬
    }
};

int find(int parent[], int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent, parent[x]);  // 경로 압축
}

void unionSets(int parent[], int rank[], int u, int v) {
    int rootU = find(parent, u);
    int rootV = find(parent, v);

    if (rootU != rootV) {
        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

int kruskalMST(vector<Edge>& edges, int V) {
    sort(edges.begin(), edges.end());  // 간선을 가중치 기준으로 정렬
    int parent[V], rank[V];
    for (int i = 0; i < V; i++) {
        parent[i] = i;  // 각 정점의 부모를 자기 자신으로 초기화
        rank[i] = 0;
    }

    int mst_weight = 0;
    for (auto& edge : edges) {
        if (find(parent, edge.u) != find(parent, edge.v)) {  // 두 정점이 다른 집합에 속하면
            mst_weight += edge.weight;
            unionSets(parent, rank, edge.u, edge.v);  // 두 정점을 같은 집합으로 합침
        }
    }

    return mst_weight;
}

프림 알고리즘 (Prim’s Algorithm)

한 정점에서 시작하여, 현재의 MST에 가장 가까운 정점을 추가해 나가는 방식
그리디 알고리즘을 기반으로 하며, 주로 우선순위 큐(Priority Queue) 를 사용하여 최소 비용 간선을 찾음

시간 복잡도
우선순위 큐 사용 시: O((V + E) log V)
전체 시간 복잡도: O(E log V) (V는 정점의 개수, E는 간선의 개수)

#include <bits/stdc++.h>
using namespace std;

int primMST(vector<vector<pair<int, int>>>& adj, int V) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<bool> inMST(V, false);  // MST에 포함 여부 체크
    vector<int> key(V, INT_MAX);  // 각 정점에 대한 최소 가중치

    pq.push({0, 0});  // 시작 정점 (가중치, 정점)
    key[0] = 0;

    int mst_weight = 0;

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

        if (inMST[u]) continue;  // 이미 MST에 포함된 경우 스킵
        inMST[u] = true;
        mst_weight += key[u];  // MST 가중치에 추가

        for (auto& [weight, v] : adj[u]) {  // 인접한 모든 정점에 대해
            if (!inMST[v] && key[v] > weight) {
                key[v] = weight;  // 최소 가중치 업데이트
                pq.push({key[v], v});  // 우선순위 큐에 추가
            }
        }
    }

    return mst_weight;
}

동작 예시

그래프

정점: {A, B, C, D, E, F}
간선:
{A, B} = 4
{A, F} = 2
{B, C} = 6
{B, D} = 3
{C, D} = 1
{D, E} = 5
{E, F} = 4

크루스칼 알고리즘을 사용한 MST

1. 간선 정렬: {C-D: 1}, {A-F: 2}, {B-D: 3}, {A-B: 4}, {E-F: 4}, {D-E: 5}, {B-C: 6}
2. 사이클이 발생하지 않는 간선을 순서대로 추가
   • MST: {C-D: 1}, {A-F: 2}, {B-D: 3}, {A-B: 4}, {D-E: 5}
   • MST의 총 가중치: 15

프림 알고리즘을 사용한 MST

1. 임의의 정점(A)에서 시작
2. A와 연결된 간선 중 최소 가중치 간선 {A-F: 2} 선택
3. F와 연결된 간선 중 최소 가중치 간선 {F-E: 4} 선택
4. E와 연결된 간선 중 {E-D: 5} 선택
5. D와 연결된 간선 중 {D-C: 1} 선택
6. D와 연결된 간선 중 {D-B: 3} 선택
7. MST의 총 가중치: 15