기본 개념

주어진 무방향 그래프 \( G = (V, E) \) 에 대해, 모든 정점이 연결된 부분 그래프 \( G' = (V, E') \) 중에서 간선 가중치의 합이 최소인 트리를 찾는 문제를 최소 신장 트리(Minimum Spanning Tree, MST)라고 한다. 이는 \( |V| \)개의 정점과 \( |V|-1 \)개의 간선으로 구성되며 사이클이 없고 연결되어야 한다.

Prim 알고리즘 (밀도 높은 그래프에 적합)

기본 아이디어: 하나의 정점부터 시작하여 현재까지 포함된 정점 집합과 연결되는 가장 작은 가중치의 간선을 반복적으로 선택한다.

• 초기화: 임의의 정점부터 시작해, 그 정점만 포함된 집합 \( V \)와 빈 간선 집합 \( E \)를 설정한다.
• 반복: 현재 \( V \) 내부에 있는 정점과 외부에 있는 정점 사이에서 가중치가 가장 작은 간선 \( e = (u, v) \)를 찾는다. 이 간선을 \( E \)에 추가하고 \( v \)를 \( V \)에 포함시킨다.
• 종료 조건: \( V \)에 모든 정점이 포함되면 종료, 그렇지 않으면 계속 반복.

시간 복잡도

• 기본 구현: \( \Theta(V^2) \)
• 우선순위 큐 사용 시: \( \Theta(E \log V) \)
• 피보나치 힙 사용 시: \( \Theta(E + V \log V) \)

정당성 증명 요약

Prim이 생성한 트리 \( P \)와 최적 트리 \( T \)가 다르다고 가정하고, 첫 번째로 다를 때의 간선을 비교하면, \( T \)에서 해당 간선보다 더 작은 가중치의 간선을 교체할 수 있거나, 동일한 가중치일 경우 교체 가능하다. 결국 \( T \)를 \( P \)로 변환하면서 가중치는 유지되므로 \( P \) 역시 최적이다.

코드 구현 (입력: 인접 행렬)

const int INF = 0x3f3f3f3f;
const int MAX_N = 110;

int n;
int graph[MAX_N][MAX_N];
int dist[MAX_N];
bool visited[MAX_N];
int totalWeight = 0;

void prim_mst() {
    std::fill(dist, dist + MAX_N, INF);
    dist[1] = 0;

    for (int i = 1; i <= n; ++i) {
        int u = -1;
        for (int j = 1; j <= n; ++j)
            if (!visited[j] && (u == -1 || dist[j] < dist[u]))
                u = j;

        if (u == -1) {
            // 그래프가 비연결 상태
            throw std::runtime_error("Graph is not connected");
        }

        visited[u] = true;
        totalWeight += dist[u];

        for (int v = 1; v <= n; ++v)
            if (!visited[v] && graph[u][v] < dist[v])
                dist[v] = graph[u][v];
    }
}

Kruskal 알고리즘 (희소 그래프에 적합)

기본 아이디어: 모든 간선을 가중치 순으로 정렬한 후, 사이클이 생기지 않는 범위 내에서 차례로 간선을 선택한다.

• 정렬: 모든 간선을 가중치 기준으로 오름차순 정렬.
• 선택: 각 간선을 순서대로 고려하며, 두 정점이 이미 같은 연결 컴포넌트에 속해 있지 않은 경우에만 선택 (사이클 방지).
• 종료: \( n-1 \)개의 간선이 선택되었을 때 종료.

시간 복잡도

• 간선 정렬: \( \Theta(E \log E) \)
• Union-Find 연산: \( \Theta(E \alpha(n)) \), 여기서 \( \alpha \)는 아커만 함수의 역함수
• 전체: \( \Theta(E \log E) \)

정당성 증명 개요

크루스칼이 생성한 트리 \( K \)와 최적 트리 \( T \)가 다를 경우, \( K \)에 있지만 \( T \)에 없는 최소 가중치 간선 \( e \)를 찾는다. \( e \)를 \( T \)에 추가하면 사이클이 생기며, 이 사이클 내에서 \( K \)에 없는 간선 \( e' \)를 제거하면 새로운 트리 \( T' \)가 만들어진다. 이때 \( w(e') > w(e) \)면 \( T' \)이 더 작아지며 모순, \( w(e') < w(e) \)면 크루스칼이 먼저 \( e' \)을 선택했어야 하므로 모순. 따라서 \( w(e') = w(e) \)이며, \( T \)를 \( K \)로 바꾸는 과정이 가능하다.

코드 구현 (간선 리스트 + Union-Find)

struct Edge {
    int from, to, weight;
    
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

Edge edges[MAX_N * MAX_N / 2];
Edge mst_edges[MAX_N];
int n, edge_count, mst_edge_count;
int parent[MAX_N];
int total_weight = 0;

int find_root(int x) {
    return parent[x] == x ? x : parent[x] = find_root(parent[x]);
}

void kruskal_mst() {
    mst_edge_count = 0;
    total_weight = 0;
    std::sort(edges, edges + edge_count);

    for (int i = 1; i <= n; ++i)
        parent[i] = i;

    for (int i = 0; i < edge_count; ++i) {
        int u = find_root(edges[i].from);
        int v = find_root(edges[i].to);

        if (u == v) continue;

        mst_edges[mst_edge_count++] = edges[i];
        total_weight += edges[i].weight;
        parent[u] = v;

        if (mst_edge_count == n - 1)
            break;
    }
}