Kruskal 알고리즘

희소 그래프(Sparse Graph)에 적합한 크루스칼 알고리즘은 간선 기반의 탐욕적 접근 방식을 사용한다. 모든 간선을 가중치 기준으로 오름차순 정렬한 후, 사이클을 만들지 않는 한도 내에서 순차적으로 선택한다. 이때 연결 여부는 유니온-파인드(Union-Find) 자료구조로 관리한다.

n개의 정점이 주어졌을 때, 최소 스패닝 트리는 정확히 n-1개의 간선으로 구성되므로, 해당 조건을 만족할 때까지 반복한다.

#include <queue>
#include <algorithm>

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const { return w > other.w; }
};

int parent[100001];

int findRoot(int x) {
    if (parent[x] != x) parent[x] = findRoot(parent[x]);
    return parent[x];
}

void merge(int a, int b) {
    a = findRoot(a), b = findRoot(b);
    if (a != b) parent[a] = b;
}

long long kruskal(const vector<Edge>& edges, int n) {
    priority_queue<Edge> pq(edges.begin(), edges.end());
    for (int i = 1; i <= n; ++i) parent[i] = i;

    long long totalWeight = 0;
    int selectedEdges = 0;

    while (selectedEdges < n - 1 && !pq.empty()) {
        Edge e = pq.top(); pq.pop();
        if (findRoot(e.u) != findRoot(e.v)) {
            merge(e.u, e.v);
            totalWeight += e.w;
            ++selectedEdges;
        }
    }

    return selectedEdges == n - 1 ? totalWeight : -1; // 불가능 시 -1 반환
}

시간 복잡도는 간선 정렬 비용 때문에 O(m \log m)이며, 완전 그래프에서는 O(n^2 \log n) 수준으로 증가한다.

Prim 알고리즘

밀집 그래프(Dense Graph)에서 더 효율적인 프림 알고리즘은 정점 중심의 전략을 취한다. 하나의 시작 정점을 기준으로 하여, 현재 MST에 포함되지 않은 정점 중 MST와 가장 가까운 정점을 반복적으로 추가한다.

각 단계에서 거리 배열 dist[]을 갱신하며, 아직 선택되지 않은 정점 중 최소 값을 선택하는 방식으로 진행된다. 이를 위해 방문 상태를 추적하는 visited[] 배열이 필요하다.

#include <vector>
#include <climits>

const int MAXN = 5001;
const int INF = INT_MAX;

vector<pair<int, int>> adj[MAXN]; // 인접 리스트: {정점, 가중치}
bool visited[MAXN];
int dist[MAXN];

long long prim(int n) {
    fill(dist, dist + n + 1, INF);
    dist[1] = 0;
    long long totalWeight = 0;

    for (int step = 0; step < n; ++step) {
        int u = -1;
        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && (u == -1 || dist[v] < dist[u])) {
                u = v;
            }
        }

        if (u == -1 || dist[u] == INF) return -1; // 연결 불가

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

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (!visited[v] && w < dist[v]) {
                dist[v] = w;
            }
        }
    }

    return totalWeight;
}

기본 구현의 시간 복잡도는 O(n^2)이며, 힙을 사용하면 O((n + m) \log n)으로 개선 가능하지만 밀집 그래프에서는 제곱 시간이 충분히 효율적이다.

Boruvka 알고리즘

보루브카 알고리즘은 분산 처리에 유리한 병렬화 친화적 구조를 지닌다. 초기에는 각 정점이 독립된 컴포넌트로 시작하며, 매 반복마다 각 컴포넌트가 다른 컴포넌트로 향하는 최소 가중치 간선을 찾아 연결한다.

매 단계에서 컴포넌트 수가 최소 절반 이상 줄어들기 때문에, 전체 반복 횟수는 O(\log n)이다. 각 단계에서 모든 간선을 검사하므로 총 시간 복잡도는 O(m \log n).

int comp[100001], minEdge[100001], toComp[100001];
Edge edges[200001];

int findComp(int x) {
    while (x != comp[x]) x = comp[x] = comp[comp[x]];
    return x;
}

bool unionComps(int a, int b) {
    a = findComp(a), b = findComp(b);
    if (a == b) return false;
    if (a > b) swap(a, b);
    comp[b] = a;
    return true;
}

long long boruvka(vector<Edge> edgeList, int n, int m) {
    for (int i = 1; i <= n; ++i) {
        comp[i] = i;
        minEdge[i] = INF;
    }

    long long totalWeight = 0;
    int components = n;

    while (components > 1) {
        fill(minEdge + 1, minEdge + n + 1, INF);
        fill(toComp + 1, toComp + n + 1, 0);

        for (const auto& e : edgeList) {
            int c1 = findComp(e.u), c2 = findComp(e.v);
            if (c1 != c2) {
                if (e.w < minEdge[c1]) {
                    minEdge[c1] = e.w;
                    toComp[c1] = c2;
                }
                if (e.w < minEdge[c2]) {
                    minEdge[c2] = e.w;
                    toComp[c2] = c1;
                }
            }
        }

        bool merged = false;
        for (int i = 1; i <= n; ++i) {
            if (findComp(i) == i && toComp[i]) {
                if (unionComps(i, toComp[i])) {
                    totalWeight += minEdge[i];
                    --components;
                    merged = true;
                }
            }
        }

        if (!merged) break; // 더 이상 연결 불가
    }

    return components == 1 ? totalWeight : -1;
}

고급 응용: XOR 최소 스패닝 트리

특수한 형태의 문제, 예를 들어 CF888G Xor-MST처럼 두 정점 간의 간선 비용이 a_i \oplus a_j로 주어지는 경우, 일반적인 알고리즘은 비효율적이다. 이때 보루브카 알고리즘의 구조를 유지하면서 내부 간선 탐색 과정을 최적화할 수 있다.

핵심 아이디어는 각 컴포넌트의 정점들을 Trie에 저장하고, 특정 정점과 가장 작은 XOR 값을 갖는 다른 컴포넌트의 정점을 O(\log A) 시간에 찾는 것이다. 또한, Trie 병합을 통해 컴포넌트 통합 시에도 효율성을 유지한다.

전체 시간 복잡도는 O(n \log A \log n)이며, 상수 최적화된 분할 정복 기법으로 더욱 빠르게 해결할 수도 있다.