用C语言实现题目3：最小生成树 问题描述 用Kruskal算法求无向连通图的最小生成树。 输入格式 输入数据第一行为一个正整数，表示图中边的数目n。之后是n行输入数据：每行都是两个大写的英文字符（A-Z中的字符）和一个整数，中间都用一个空格隔开，两个大写字符表示一条边的起点和终点，整数表示该边的边长。 输出格式 按照Kruskal算法的求解次序输出最小生成树的所有边和边长之和。要求：（1）每行输出一条边，输出边的格式为起点、终点字符与边长，中间用空格隔开；（2） 输出边的起点终点字符必须与输入时一致，例如输入一条边“A B 2”，如果这条边在最小生成树中，输出必须是“A B 2”，而不是“B A 2”；（3）先输出各边，最后在一行上输出最小生成树的边长之和。

以下是用C语言实现Kruskal算法求解无向连通图最小生成树的代码，供您参考：

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

#define MAX_EDGE_NUM 10000
#define MAX_VERTEX_NUM 26

typedef struct {
    int start;  /* 边的起点 */
    int end;    /* 边的终点 */
    int weight; /* 边的权值 */
} Edge;

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

int find(int *parent, int idx) {
    if (parent[idx] != idx) {
        parent[idx] = find(parent, parent[idx]);
    }
    return parent[idx];
}

void union_set(int *parent, int p, int q) {
    int root_p = find(parent, p);
    int root_q = find(parent, q);
    if (root_p == root_q) {
        return;
    }
    parent[root_q] = root_p;
}

void kruskal(Edge *edges, int edge_num, int vertex_num) {
    int parent[MAX_VERTEX_NUM];
    for (int i = 0; i < vertex_num; ++i) {
        parent[i] = i;
    }

    int selected_edge_num = 0; /* 已选择的边的数量 */
    int selected_edge_weight_sum = 0; /* 已选择的边的权值之和 */

    for (int i = 0; i < edge_num; ++i) {
        int p = edges[i].start - 'A';
        int q = edges[i].end - 'A';
        if (find(parent, p) != find(parent, q)) {
            union_set(parent, p, q);
            printf("%c %c %d\n", edges[i].start, edges[i].end, edges[i].weight);
            selected_edge_num++;
            selected_edge_weight_sum += edges[i].weight;
            if (selected_edge_num == vertex_num - 1) {
                break;
            }
        }
    }

    printf("%d\n", selected_edge_weight_sum);
}

int main() {
    int edge_num, vertex_num = 0;
    Edge edges[MAX_EDGE_NUM];

    scanf("%d", &edge_num);
    for (int i = 0; i < edge_num; ++i) {
        char start, end;
        int weight;
        scanf("%s %s %d", &start, &end, &weight);
        edges[i].start = start;
        edges[i].end = end;
        edges[i].weight = weight;
        if (start - 'A' + 1 > vertex_num) {
            vertex_num = start - 'A' + 1;
        }
        if (end - 'A' + 1 > vertex_num) {
            vertex_num = end - 'A' + 1;
        }
    }

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

    kruskal(edges, edge_num, vertex_num);

    return 0;
}

代码说明：

1. 定义 `Edge` 结构体表示图中的一条边，包括起点、终点和权值。
2. 定义 `cmp` 函数作为 `qsort` 函数的比较函数，用于按照边的权值从小到大排序。
3. 定义 `find` 函数和 `union_set` 函数，用于并查集的查找和合并操作。
4. 定义 `kruskal` 函数，实现Kruskal算法求解最小生成树。
5. 在 `main` 函数中读入图的边信息，按照边的权值从小到大排序，并调用 `kruskal` 函数求解最小生成树。