프림 알고리즘 (인접 행렬 기반)

다익스트라 알고리즘과 유사하지만, 거리 업데이트 대상이 다른 점이 핵심이다. 프림은 현재 신장 트리에 포함된 정점들과 연결된 간선 중 최소 가중치를 선택하여 확장한다.

크루스칼 알고리즘

Union-Find 자료구조를 활용하며, 모든 간선을 가중치 기준으로 오름차순 정렬한다. 두 정점이 이미 같은 연결 컴포넌트에 속해 있으면 간선을 건너뛰고, 그렇지 않으면 추가한다.

가장 큰 간선 가중치를 최소화하기

모든 정점이 연결되도록 하는 조건 하에서, 가장 큰 간선의 가중치를 최소화하는 문제는 크루스칼 알고리즘을 통해 해결할 수 있다.

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

const int MAX_N = 16005;
int n, m;
struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
} edges[MAX_N];

int parent[MAX_N];

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

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        parent[i] = i;

    for (int i = 0; i < m; ++i)
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;

    sort(edges, edges + m);

    int max_edge = 0;
    for (int i = 0; i < m; ++i) {
        int root_u = find(edges[i].u);
        int root_v = find(edges[i].v);
        if (root_u != root_v) {
            parent[root_u] = root_v;
            max_edge = edges[i].weight;
        }
    }

    cout << n - 1 << " " << max_edge;
    return 0;
}

필수 연결 간선 처리 및 축소

미리 연결되어야 하는 간선(필수 간선)을 먼저 처리하고, 나머지 간선들에 대해 크루스칼 알고리즘을 적용한다.

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

const int MAX_N = 10005;
int n, m;
int parent[MAX_N];
struct Edge {
    int u, v, cost;
} edges[MAX_N];

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

int main() {
    cin >> n >> m;
    int total_cost = 0;
    int edge_count = 0;

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

    for (int i = 0; i < m; ++i) {
        int type, a, b, c;
        cin >> type >> a >> b >> c;
        if (type == 1) {
            parent[find(a)] = find(b);
            total_cost += c;
        } else {
            edges[edge_count++] = {a, b, c};
        }
    }

    sort(edges, edges + edge_count);

    for (int i = 0; i < edge_count; ++i) {
        int root_a = find(edges[i].u);
        int root_b = find(edges[i].v);
        if (root_a != root_b) {
            parent[root_a] = root_b;
            total_cost += edges[i].cost;
        }
    }

    cout << total_cost;
    return 0;
}

수직/수평 연결 비용 다름: 작은 비용 우선 연결

격자 구조에서 수직과 수평 연결의 비용이 다를 때, 비용이 낮은 방향부터 우선 연결해야 한다.

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

const int MAX_N = 1010;
const int MAX_K = 2 * MAX_N * MAX_N;
const int MAX_M = MAX_N * MAX_N;

int n, m, k;
int id[MAX_N][MAX_N];
struct Edge {
    int u, v, cost;
} edges[MAX_K];

int parent[MAX_M];

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

void generate_edges() {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, costs[4] = {1, 2, 1, 2};

    for (int dir = 0; dir < 2; ++dir) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                for (int d = 0; d < 4; ++d) {
                    if (d % 2 == dir) {
                        int ni = i + dx[d], nj = j + dy[d];
                        if (ni >= 1 && ni <= n && nj >= 1 && nj <= m) {
                            int a = id[i][j], b = id[ni][nj];
                            if (a < b) {
                                edges[k++] = {a, b, costs[d]};
                            }
                        }
                    }
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 1, idx = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j, ++idx)
            id[i][j] = idx;

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

    int x1, y1, x2, y2;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        int a = id[x1][y1], b = id[x2][y2];
        parent[find(a)] = find(b);
    }

    generate_edges();
    sort(edges, edges + k);

    int result = 0;
    for (int i = 0; i < k; ++i) {
        int a = find(edges[i].u), b = find(edges[i].v);
        if (a != b) {
            parent[a] = b;
            result += edges[i].cost;
        }
    }

    cout << result << endl;
    return 0;
}

정점 가중치와 간선 가중치가 모두 존재할 때

정점 가중치를 가상의 원점과 연결한 간선의 가중치로 변환하여 최소 신장 트리 문제로 환원한다.

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

const int MAX_N = 305;
int graph[MAX_N][MAX_N];
int n;
int dist[MAX_N];
bool visited[MAX_N];
int parent[MAX_N];

int prim_algorithm() {
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
    int total_cost = 0;

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

        visited[min_node] = true;
        total_cost += dist[min_node];

        for (int j = 0; j <= n; ++j)
            dist[j] = min(dist[j], graph[min_node][j]);
    }

    return total_cost;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> graph[0][i];
        graph[i][0] = graph[0][i];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            cin >> graph[i][j];
    }

    cout << prim_algorithm() << endl;
    return 0;
}