用C语言编程实现构建最小生成树的两种算法，可以动态输入，解释代码

好的，下面我来介绍两种C语言编程实现构建最小生成树的算法：Prim算法和Kruskal算法。

### Prim算法

Prim算法（普里姆算法）是一种求解加权无向连通图的最小生成树的算法。具体实现过程如下：

1. 首先任选一个顶点作为起始点，将其加入生成树中。

2. 然后找到与已经加入生成树中的顶点相连的所有边，并将这些边按照权值从小到大排序。

3. 从排好序的边中选取一条权值最小的边，如果这条边的另一个顶点没有加入生成树中，则将其加入生成树中。

4. 重复步骤2和步骤3，直到所有顶点都被加入生成树中。

下面是Prim算法的C语言实现代码：

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

#define MAX_VERTICES 100

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

int n, m;
int parent[MAX_VERTICES + 1];
int rank[MAX_VERTICES + 1];
Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];

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

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

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

void prim() {
    int i, j, k, min, sum = 0;
    int visited[MAX_VERTICES + 1] = {0};
    Edge result[MAX_VERTICES - 1];

    for (i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

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

    visited[1] = 1;

    for (i = 1, j = 0; i < n; i++) {
        while (visited[edges[j].start] && visited[edges[j].end]) j++;
        result[i-1] = edges[j];
        visited[edges[j].start] = visited[edges[j].end] = 1;
        sum += edges[j].weight;
        j++;
    }

    printf("Minimum spanning tree:\n");
    for (i = 0; i < n-1; i++) {
        printf("(%d, %d) %d\n", result[i].start, result[i].end, result[i].weight);
    }
    printf("Minimum cost = %d\n", sum);
}

int main() {
    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);
    }

    prim();

    return 0;
}

### Kruskal算法

Kruskal算法（克鲁斯卡尔算法）也是一种求解加权无向连通图的最小生成树的算法。具体实现过程如下：

1. 将所有边按照权值从小到大排序。

2. 依次将排序好的边加入生成树中，如果这条边的两个顶点已经在生成树中，则舍弃这条边。

3. 重复步骤2，直到生成树中有n-1条边为止。

下面是Kruskal算法的C语言实现代码：

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

#define MAX_VERTICES 100

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

int n, m;
int parent[MAX_VERTICES + 1];
int rank[MAX_VERTICES + 1];
Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];

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

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

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

void kruskal() {
    int i, j, k, sum = 0;
    int count = 0;
    Edge result[MAX_VERTICES - 1];

    for (i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

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

    for (i = 0; i < m && count < n-1; i++) {
        int x = find(edges[i].start);
        int y = find(edges[i].end);
        if (x != y) {
            result[count++] = edges[i];
            union_set(x, y);
            sum += edges[i].weight;
        }
    }

    printf("Minimum spanning tree:\n");
    for (i = 0; i < n-1; i++) {
        printf("(%d, %d) %d\n", result[i].start, result[i].end, result[i].weight);
    }
    printf("Minimum cost = %d\n", sum);
}

int main() {
    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);
    }

    kruskal();

    return 0;
}

以上就是Prim算法和Kruskal算法的C语言实现代码。需要注意的是，这两个算法中都用到了并查集来管理连通性，因此需要实现并查集的两个函数：find和union_set。在这里我使用了路径压缩和按秩合并来优化并查集。