#include stdioh#include stdlibh#define MAX_VERTEX_NUM 100 最大顶点数#define INF 32767 表示无穷大的值typedef struct int vex1; 边的起点 int vex2; 边的终点 int weight; 边的权值 Edge; 边的结构体typedef struct int

本代码实现了Kruskal算法，用于求解无向图的最小生成树。具体注释如下：

1. 定义边的结构体Edge，包括边的起点、终点和权值。

typedef struct { int vex1; // 边的起点 int vex2; // 边的终点 int weight; // 边的权值 } Edge; // 边的结构体

2. 定义图的结构体Graph，包括顶点、边的权值等信息。

typedef struct { int vex[MAX_VERTEX_NUM]; // 存储顶点 int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值 int vexNum; // 顶点数 int edgeNum; // 边数 } Graph; // 图的结构体

3. 初始化图，将所有边的权值初始化为INF，顶点数和边数初始化为0。

void initGraph(Graph* graph) { int i, j; for (i = 0; i < MAX_VERTEX_NUM; i++) { for (j = 0; j < MAX_VERTEX_NUM; j++) { graph->edge[i][j] = INF; } } graph->vexNum = 0; graph->edgeNum = 0; }

4. 定义find函数，用于查找某个顶点的父节点。

int find(int* parent, int f) { while (parent[f] > 0) { f = parent[f]; } return f; }

5. 定义Kruskal算法，用于求解无向图的最小生成树。

void kruskal(Graph graph, Edge* mst) { int i, j, k, n, m; int parent[MAX_VERTEX_NUM] = { 0 }; // 存储每个顶点的父节点 Edge* edgeList = (Edge*)malloc(sizeof(Edge) * graph.edgeNum); // 存储所有边的列表 k = 0; // 边的数量 for (i = 0; i < graph.vexNum; i++) { for (j = i + 1; j < graph.vexNum; j++) { if (graph.edge[i][j] != INF) { // 存储所有的边 edgeList[k].vex1 = i; edgeList[k].vex2 = j; edgeList[k].weight = graph.edge[i][j]; k++; } } } for (i = 0; i < k; i++) { // 对所有边按权值从小到大排序 for (j = i + 1; j < k; j++) { if (edgeList[i].weight > edgeList[j].weight) { Edge temp = edgeList[i]; edgeList[i] = edgeList[j]; edgeList[j] = temp; } } } k = 0; // 选中的边的数量 for (i = 0; i < graph.edgeNum; i++) { int parentVex1 = find(parent, edgeList[i].vex1); int parentVex2 = find(parent, edgeList[i].vex2); if (parentVex1 != parentVex2) { // 如果两个顶点的父节点不同，说明它们不在同一个集合中 parent[parentVex1] = parentVex2; // 将它们合并到同一个集合中 mst[k++] = edgeList[i]; // 将该边加入最小生成树 if (k == graph.vexNum - 1) { // 最小生成树的边数等于顶点数减1时结束 break; } } } free(edgeList); }

6. 主函数中读取输入信息，调用Kruskal算法，输出最小生成树的边及其权值。

int main() { Graph graph; Edge mst[MAX_VERTEX_NUM - 1]; int i, j; initGraph(&graph); printf("请输入顶点数和边数："); scanf("%d%d", &graph.vexNum, &graph.edgeNum); printf("请输入顶点："); for (i = 0; i < graph.vexNum; i++) { scanf("%d", &graph.vex[i]); } printf("请输入边及其权值：\n"); for (i = 0; i < graph.edgeNum; i++) { int vex1, vex2, weight; scanf("%d%d%d", &vex1, &vex2, &weight); graph.edge[vex1][vex2] = weight; graph.edge[vex2][vex1] = weight; // 无向图的边是双向的 } kruskal(graph, mst); printf("最小生成树的边及其权值为：\n"); for (i = 0; i < graph.vexNum - 1; i++) { printf("(%d, %d) %d\n", graph.vex[mst[i].vex1], graph.vex[mst[i].vex2], mst[i].weight); } return 0;