C语言程序最小生成树

以下是C语言程序实现最小生成树的例子：

1. Kruskal算法实现最小生成树

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

#define MAX 1000

typedef struct {
    int u, v, w;
} Edge;

Edge edge[MAX];
int parent[MAX], rank[MAX];

int cmp(const void *a, const void *b) {
    return ((Edge *)a)->w - ((Edge *)b)->w;
}

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

void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (rank[px] > rank[py]) {
        parent[py] = px;
    } else {
        parent[px] = py;
        if (rank[px] == rank[py]) {
            rank[py]++;
        }
    }
}

void kruskal(int n, int m) {
    int i, cnt = 0;
    for (i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    qsort(edge, m, sizeof(Edge), cmp);
    for (i = 0; i < m; i++) {
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (find(u) != find(v)) {
            merge(u, v);
            printf("%d %d %d\n", u, v, w);
            cnt++;
            if (cnt == n - 1) {
                break;
            }
        }
    }
}

int main() {
    int n, m, i;
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    }
    kruskal(n, m);
    return 0;
}

2. Prim算法实现最小生成树

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

#define MAX 1000
#define INF 0x3f3f3f3f

int graph[MAX][MAX], dist[MAX], visited[MAX];

void prim(int n) {
    int i, j, k, min;
    memset(dist, INF, sizeof(dist));
    memset(visited, 0, sizeof(visited));
    dist[1] = 0;
    for (i = 1; i <= n; i++) {
        min = INF;
        for (j = 1; j <= n; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                k = j;
            }
        }
        visited[k] = 1;
        for (j = 1; j <= n; j++) {
            if (!visited[j] && graph[k][j] < dist[j]) {
                dist[j] = graph[k][j];
            }
        }
    }
    for (i = 2; i <= n; i++) {
        printf("%d %d %d\n", i, parent[i], dist[i]);
    }
}

int main() {
    int n, m, i, u, v, w;
    scanf("%d%d", &n, &m);
    memset(graph, INF, sizeof(graph));
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = graph[v][u] = w;
    }
    prim(n);
    return 0;
}