用c语言编译实现构建最小生成树的两种算法自己输入数据

好的，我可以为您编写两种算法的 C 代码，并让您输入数据进行测试。以下是代码：

### Kruskal算法

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

// 定义边
struct Edge {
    int u, v, w;
};

// 定义并查集
struct UnionFind {
    int *parent;
    int *size;
};

// 初始化并查集
void makeSet(struct UnionFind *uf, int n) {
    uf->parent = (int *)malloc(sizeof(int) * n);
    uf->size = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->size[i] = 1;
    }
}

// 查找根节点
int find(struct UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

// 合并两个集合
void merge(struct UnionFind *uf, int x, int y) {
    int rootX = find(uf, x);
    int rootY = find(uf, y);
    if (rootX == rootY) {
        return;
    }
    if (uf->size[rootX] > uf->size[rootY]) {
        int temp = rootX;
        rootX = rootY;
        rootY = temp;
    }
    uf->parent[rootX] = rootY;
    uf->size[rootY] += uf->size[rootX];
}

// 比较函数，用于排序边
int cmp(const void *a, const void *b) {
    return (*(struct Edge *)a).w - (*(struct Edge *)b).w;
}

// Kruskal算法
void kruskal(struct Edge *edges, int n, int m) {
    struct UnionFind uf;
    makeSet(&uf, n);
    int count = 0;
    for (int i = 0; i < m; i++) {
        if (count == n - 1) {
            break;
        }
        int u = edges[i].u;
        int v = edges[i].v;
        if (find(&uf, u) != find(&uf, v)) {
            merge(&uf, u, v);
            printf("%d %d %d\n", u, v, edges[i].w);
            count++;
        }
    }
    free(uf.parent);
    free(uf.size);
}

int main() {
    int n, m;
    printf("请输入节点数和边数：");
    scanf("%d %d", &n, &m);
    struct Edge *edges = (struct Edge *)malloc(sizeof(struct Edge) * m);
    printf("请依次输入每条边的起点、终点、权值：\n");
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }
    qsort(edges, m, sizeof(struct Edge), cmp);
    printf("最小生成树的边为：\n");
    kruskal(edges, n, m);
    free(edges);
    return 0;
}

### Prim算法

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

// 定义邻接矩阵
int **adj;

// Prim算法
void prim(int n) {
    int *visited = (int *)malloc(sizeof(int) * n);
    int *dist = (int *)malloc(sizeof(int) * n);
    int *parent = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
        dist[i] = INT_MAX;
        parent[i] = -1;
    }
    dist[0] = 0;
    for (int i = 0; i < n - 1; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = 1;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && adj[u][v] < dist[v]) {
                dist[v] = adj[u][v];
                parent[v] = u;
            }
        }
    }
    printf("最小生成树的边为：\n");
    for (int i = 1; i < n; i++) {
        printf("%d %d %d\n", parent[i], i, adj[parent[i]][i]);
    }
    free(visited);
    free(dist);
    free(parent);
}

int main() {
    int n, m;
    printf("请输入节点数和边数：");
    scanf("%d %d", &n, &m);
    adj = (int **)malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++) {
        adj[i] = (int *)malloc(sizeof(int) * n);
        for (int j = 0; j < n; j++) {
            adj[i][j] = INT_MAX;
        }
    }
    printf("请依次输入每条边的起点、终点、权值：\n");
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u][v] = w;
        adj[v][u] = w;
    }
    prim(n);
    for (int i = 0; i < n; i++) {
        free(adj[i]);
    }
    free(adj);
    return 0;
}

您可以自行输入数据进行测试。