33. Kruskal 알고리즘

Kruskal 알고리즘은 그리디 알고리즘을 사용하여 최소비용 신장 트리를 구하는 알고리즘이다.

이 알고리즘은 그래프의 간선을 가중치의 오름차순으로 정렬한 뒤, 사이클을 생성하지 않는 작은 가중치 간선부터 선택하여 트리를 만드는 방식으로 동작한다.

 

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100
#define MAX_EDGES 100

typedef struct {
    int start, end, weight;
} Edge;

int parent[MAX_VERTICES];

int cmp(const void* a, const void* b) {
    Edge* x = (Edge*)a;
    Edge* y = (Edge*)b;
    return x->weight - y->weight;
}

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

void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    parent[u] = v;
}

int kruskal(int n, Edge* edges, int m, Edge* selected) {
    int total_weight = 0;
    int e = 0;
    int i;

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

    qsort(edges, m, sizeof(Edge), cmp);

    for (i = 0; i < m; i++) {
        int u = edges[i].start;
        int v = edges[i].end;
        int weight = edges[i].weight;

        if (find(u) == find(v)) continue;

        merge(u, v);
        selected[e++] = edges[i];
        total_weight += weight;

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

    return total_weight;
}

int main() {
    int n, m;
    Edge edges[MAX_EDGES];
    Edge selected[MAX_EDGES];
    int total_weight;
    int i;

    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].start, &edges[i].end, &edges[i].weight);
    }

    total_weight = kruskal(n, edges, m, selected);

    printf("Total weight: %d\n", total_weight);
    for (i = 0; i < n - 1; i++) {
        printf("(%d, %d) %d\n", selected[i].start, selected[i].end, selected[i].weight);
    }

    return 0;
}