C语言实现最小生成树算法 - 普利姆算法和克鲁斯卡尔算法

#include <stdio.h>\n#include <stdlib.h>\n\n// 定义最大城市数\n#define MAX_CITY 10\n\n// 定义邻接表的结点结构\ntypedef struct Node {\n int city; // 城市编号\n int distance; // 城市之间的距离\n struct Node* next; // 指向下一个结点的指针\n} Node;\n\n// 定义邻接表的头结点结构\ntypedef struct HeadNode {\n struct Node* first; // 指向第一个结点的指针\n} HeadNode;\n\n// 定义边的结构\ntypedef struct Edge {\n int city1; // 城市1\n int city2; // 城市2\n int distance; // 城市之间的距离\n} Edge;\n\n// 定义并查集的结点结构\ntypedef struct UnionFindNode {\n int parent; // 结点的父结点\n int rank; // 结点的秩\n} UnionFindNode;\n\n// 初始化邻接表的头结点数组\nvoid initHeadNodes(HeadNode* headNodes, int n) {\n for (int i = 0; i < n; i++) {\n headNodes[i].first = NULL;\n }\n}\n\n// 向邻接表中插入边\nvoid insertEdge(HeadNode* headNodes, int city1, int city2, int distance) {\n // 创建新结点\n Node* newNode = (Node*)malloc(sizeof(Node));\n newNode->city = city2;\n newNode->distance = distance;\n newNode->next = headNodes[city1].first;\n headNodes[city1].first = newNode;\n}\n\n// 打印邻接表\nvoid printAdjacencyList(HeadNode* headNodes, int n) {\n for (int i = 0; i < n; i++) {\n printf("城市%d:", i);\n Node* node = headNodes[i].first;\n while (node != NULL) {\n printf(" 城市%d 距离%d", node->city, node->distance);\n node = node->next;\n }\n printf("\n");\n }\n}\n\n// 初始化并查集\nvoid initUnionFind(UnionFindNode* unionFind, int n) {\n for (int i = 0; i < n; i++) {\n unionFind[i].parent = i;\n unionFind[i].rank = 0;\n }\n}\n\n// 查找结点的根结点（路径压缩）\nint findRoot(UnionFindNode* unionFind, int x) {\n if (unionFind[x].parent != x) {\n unionFind[x].parent = findRoot(unionFind, unionFind[x].parent);\n }\n return unionFind[x].parent;\n}\n\n// 合并两个集合（按秩合并）\nvoid unionSets(UnionFindNode* unionFind, int x, int y) {\n int rootX = findRoot(unionFind, x);\n int rootY = findRoot(unionFind, y);\n if (rootX != rootY) {\n if (unionFind[rootX].rank > unionFind[rootY].rank) {\n unionFind[rootY].parent = rootX;\n } else if (unionFind[rootX].rank < unionFind[rootY].rank) {\n unionFind[rootX].parent = rootY;\n } else {\n unionFind[rootY].parent = rootX;\n unionFind[rootX].rank++;\n }\n }\n}\n\n// 比较两个边的权重（用于排序）\nint compareEdges(const void* a, const void* b) {\n Edge* edgeA = (Edge*)a;\n Edge* edgeB = (Edge*)b;\n return edgeA->distance - edgeB->distance;\n}\n\n// 使用普利姆算法构建最小生成树，并返回总权重\nint prim(HeadNode* headNodes, int n) {\n int* visited = (int*)calloc(n, sizeof(int)); // 标记结点是否被访问过\n visited[0] = 1; // 从第一个结点开始\n int totalWeight = 0; // 总权重\n for (int i = 0; i < n - 1; i++) {\n int minDistance = INT_MAX; // 最小距离\n int minCity1, minCity2; // 最小距离对应的城市\n for (int j = 0; j < n; j++) {\n if (visited[j]) {\n Node* node = headNodes[j].first;\n while (node != NULL) {\n if (!visited[node->city] && node->distance < minDistance) {\n minDistance = node->distance;\n minCity1 = j;\n minCity2 = node->city;\n }\n node = node->next;\n }\n }\n }\n visited[minCity2] = 1;\n totalWeight += minDistance;\n printf("最小生成树边: 城市%d - 城市%d 距离%d\n", minCity1, minCity2, minDistance);\n }\n free(visited);\n return totalWeight;\n}\n\n// 使用克鲁斯卡尔算法构建最小生成树，并返回总权重\nint kruskal(Edge* edges, int n, int m) {\n qsort(edges, m, sizeof(Edge), compareEdges); // 对边按权重进行排序\n UnionFindNode* unionFind = (UnionFindNode*)malloc(n * sizeof(UnionFindNode));\n initUnionFind(unionFind, n);\n int totalWeight = 0; // 总权重\n int edgeCount = 0; // 边的计数器\n for (int i = 0; i < m; i++) {\n if (findRoot(unionFind, edges[i].city1) != findRoot(unionFind, edges[i].city2)) {\n unionSets(unionFind, edges[i].city1, edges[i].city2);\n totalWeight += edges[i].distance;\n edgeCount++;\n printf("最小生成树边: 城市%d - 城市%d 距离%d\n", edges[i].city1, edges[i].city2, edges[i].distance);\n if (edgeCount == n - 1) {\n break;\n }\n }\n }\n free(unionFind);\n return totalWeight;\n}\n\nint main() {\n int n; // 城市数\n int m = 0; // 边数\n printf("输入城市数（至少5个）：");\n scanf("%d", &n);\n if (n < 5) {\n printf("错误：城市数不能少于5个。\n");\n return 0;\n }\n Edge* edges = (Edge*)malloc((n * (n - 1) / 2) * sizeof(Edge)); // 最多有n*(n-1)/2条边\n HeadNode* headNodes = (HeadNode*)malloc(n * sizeof(HeadNode)); // 邻接表的头结点数组\n initHeadNodes(headNodes, n);\n printf("输入城市之间的距离：\n");\n for (int i = 0; i < n; i++) {\n for (int j = i + 1; j < n; j++) {\n printf("城市%d - 城市%d：", i, j);\n int distance;\n scanf("%d", &distance);\n insertEdge(headNodes, i, j, distance);\n insertEdge(headNodes, j, i, distance);\n edges[m].city1 = i;\n edges[m].city2 = j;\n edges[m].distance = distance;\n m++;\n }\n }\n printf("邻接表：\n");\n printAdjacencyList(headNodes, n);\n printf("普利姆算法最小生成树:\n");\n int primWeight = prim(headNodes, n);\n printf("总权重：%d\n", primWeight);\n printf("克鲁斯卡尔算法最小生成树:\n");\n int kruskalWeight = kruskal(edges, n, m);\n printf("总权重：%d\n", kruskalWeight);\n free(edges);\n free(headNodes);\n return 0;\n