1、定义结构体类型graph‌：存储图的信息，包括顶点信息和边的信息。使用邻接矩阵表示法存储图‌。 2、实现Kruskal算法‌：按照边的权值递增的顺序，逐步添加边到最小生成树中，直到包含n-1条边为止。 3、输出结果‌：打印最小生成树的边及权值。

好的，下面是一个使用C语言实现的Kruskal算法的示例代码。该代码定义了图的结构体，使用邻接矩阵表示法存储图，并实现了Kruskal算法来找到最小生成树。 ```c #include <stdio.h> #include <stdlib.h> #define MAX_VERTICES 100 #define MAX_EDGES 1000 typedef struct { int u, v, weight; } Edge; typedef struct { int numVertices; int numEdges; int adjMatrix[MAX_VERTICES][MAX_VERTICES]; } Graph; // 初始化图 void initGraph(Graph *g, int numVertices) { g->numVertices = numVertices; g->numEdges = 0; for (int i = 0; i < numVertices; i++) { for (int j = 0; j < numVertices; j++) { g->adjMatrix[i][j] = 0; } } } // 添加边 void addEdge(Graph *g, int u, int v, int weight) { g->adjMatrix[u][v] = weight; g->adjMatrix[v][u] = weight; g->numEdges++; } // 并查集结构 typedef struct { int parent; int rank; } UnionFind; // 查找根节点 int find(UnionFind uf[], int i) { if (uf[i].parent != i) { uf[i].parent = find(uf, uf[i].parent); } return uf[i].parent; } // 合并两个集合 void unionSets(UnionFind uf[], int x, int y) { int xroot = find(uf, x); int yroot = find(uf, y); if (uf[xroot].rank < uf[yroot].rank) { uf[xroot].parent = yroot; } else if (uf[xroot].rank > uf[yroot].rank) { uf[yroot].parent = xroot; } else { uf[yroot].parent = xroot; uf[xroot].rank++; } } // 比较边的权重 int compare(const void *a, const void *b) { Edge *a1 = (Edge *)a; Edge *b1 = (Edge *)b; return a1->weight - b1->weight; } // Kruskal算法 void kruskalMST(Graph *g) { Edge edges[MAX_EDGES]; int edgeCount = 0; // 提取所有边 for (int i = 0; i < g->numVertices; i++) { for (int j = i + 1; j < g->numVertices; j++) { if (g->adjMatrix[i][j] != 0) { edges[edgeCount].u = i; edges[edgeCount].v = j; edges[edgeCount].weight = g->adjMatrix[i][j]; edgeCount++; } } } // 排序边 qsort(edges, edgeCount, sizeof(Edge), compare); // 初始化并查集 UnionFind uf[MAX_VERTICES]; for (int i = 0; i < g->numVertices; i++) { uf[i].parent = i; uf[i].rank = 0; } // 构建最小生成树 Edge mst[MAX_VERTICES]; int mstCount = 0; for (int i = 0; i < edgeCount; i++) { int u = edges[i].u; int v = edges[i].v; if (find(uf, u) != find(uf, v)) { mst[mstCount++] = edges[i]; unionSets(uf, u, v); } } // 输出最小生成树 printf("最小生成树的边及权值:\n"); for (int i = 0; i < mstCount; i++) { printf("边(%d, %d) 权值: %d\n", mst[i].u, mst[i].v, mst[i].weight); } } int main() { Graph g; initGraph(&g, 4); addEdge(&g, 0, 1, 10); addEdge(&g, 0, 2, 6); addEdge(&g, 0, 3, 5); addEdge(&g, 1, 3, 15); addEdge(&g, 2, 3, 4); kruskalMST(&g); return 0; } ```