C语言实现城市网络最小生成树：普利姆算法和克鲁斯卡尔算法

#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_CITY 100\n\n// 邻接表的结点\ntypedef struct Node {\n int city;\n int distance;\n struct Node* next;\n} Node;\n\n// 邻接表\ntypedef struct Graph {\n int numCities;\n Node** cityList;\n} Graph;\n\n// 邻接矩阵\ntypedef struct MatrixGraph {\n int numCities;\n int** matrix;\n} MatrixGraph;\n\n// 创建新的节点\nNode* newNode(int city, int distance) {\n Node* node = (Node*)malloc(sizeof(Node));\n node->city = city;\n node->distance = distance;\n node->next = NULL;\n return node;\n}\n\n// 创建邻接表\nGraph* createGraph(int numCities) {\n Graph* graph = (Graph*)malloc(sizeof(Graph));\n graph->numCities = numCities;\n graph->cityList = (Node**)malloc(numCities * sizeof(Node*));\n for (int i = 0; i < numCities; i++) {\n graph->cityList[i] = NULL;\n }\n return graph;\n}\n\n// 创建邻接矩阵\nMatrixGraph* createMatrixGraph(int numCities) {\n MatrixGraph* graph = (MatrixGraph*)malloc(sizeof(MatrixGraph));\n graph->numCities = numCities;\n graph->matrix = (int**)malloc(numCities * sizeof(int*));\n for (int i = 0; i < numCities; i++) {\n graph->matrix[i] = (int*)malloc(numCities * sizeof(int));\n for (int j = 0; j < numCities; j++) {\n graph->matrix[i][j] = 0;\n }\n }\n return graph;\n}\n\n// 添加边到邻接表\nvoid addEdge(Graph* graph, int city1, int city2, int distance) {\n Node* newNode1 = newNode(city2, distance);\n newNode1->next = graph->cityList[city1];\n graph->cityList[city1] = newNode1;\n \n Node* newNode2 = newNode(city1, distance);\n newNode2->next = graph->cityList[city2];\n graph->cityList[city2] = newNode2;\n}\n\n// 添加边到邻接矩阵\nvoid addEdgeToMatrix(MatrixGraph* graph, int city1, int city2, int distance) {\n graph->matrix[city1][city2] = distance;\n graph->matrix[city2][city1] = distance;\n}\n\n// 打印邻接表\nvoid printGraph(Graph* graph) {\n printf("邻接表：\n");\n for (int i = 0; i < graph->numCities; i++) {\n printf("城市 %d:", i);\n Node* node = graph->cityList[i];\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 printMatrixGraph(MatrixGraph* graph) {\n printf("邻接矩阵：\n");\n for (int i = 0; i < graph->numCities; i++) {\n for (int j = 0; j < graph->numCities; j++) {\n printf("%d ", graph->matrix[i][j]);\n }\n printf("\n");\n }\n}\n\n// 使用普利姆算法构建最小生成树\nvoid primMST(Graph* graph) {\n int numCities = graph->numCities;\n int selected[numCities];\n int parent[numCities];\n int key[numCities];\n\n for (int i = 0; i < numCities; i++) {\n selected[i] = 0;\n key[i] = INT_MAX;\n }\n\n key[0] = 0;\n parent[0] = -1;\n\n for (int count = 0; count < numCities - 1; count++) {\n int minKey = INT_MAX, minIndex;\n for (int i = 0; i < numCities; i++) {\n if (selected[i] == 0 && key[i] < minKey) {\n minKey = key[i];\n minIndex = i;\n }\n }\n\n selected[minIndex] = 1;\n\n Node* node = graph->cityList[minIndex];\n while (node != NULL) {\n int city = node->city;\n int distance = node->distance;\n if (selected[city] == 0 && distance < key[city]) {\n parent[city] = minIndex;\n key[city] = distance;\n }\n node = node->next;\n }\n }\n\n printf("最小生成树 (普利姆算法):\n");\n for (int i = 1; i < numCities; i++) {\n printf("%d - %d\n", parent[i], i);\n }\n}\n\n// 使用克鲁斯卡尔算法构建最小生成树\nvoid kruskalMST(MatrixGraph* graph) {\n int numCities = graph->numCities;\n int parent[numCities];\n int rank[numCities];\n\n for (int i = 0; i < numCities; i++) {\n parent[i] = i;\n rank[i] = 0;\n }\n\n int edgeCount = 0;\n int minDistance, city1, city2;\n printf("最小生成树 (克鲁斯卡尔算法):\n");\n while (edgeCount < numCities - 1) {\n minDistance = INT_MAX;\n\n for (int i = 0; i < numCities; i++) {\n for (int j = 0; j < numCities; j++) {\n if (graph->matrix[i][j] < minDistance) {\n minDistance = graph->matrix[i][j];\n city1 = i;\n city2 = j;\n }\n }\n }\n\n int root1 = city1;\n while (parent[root1] != root1) {\n root1 = parent[root1];\n }\n\n int root2 = city2;\n while (parent[root2] != root2) {\n root2 = parent[root2];\n }\n\n if (root1 != root2) {\n printf("%d - %d\n", city1, city2);\n edgeCount++;\n if (rank[root1] < rank[root2]) {\n parent[root1] = root2;\n } else if (rank[root1] > rank[root2]) {\n parent[root2] = root1;\n } else {\n parent[root2] = root1;\n rank[root1]++;\n }\n }\n\n graph->matrix[city1][city2] = INT_MAX;\n graph->matrix[city2][city1] = INT_MAX;\n }\n}\n\nint main() {\n int numCities;\n printf("请输入城市数（n>=5）：");\n scanf("%d", &numCities);\n\n if (numCities < 5) {\n printf("城市数必须大于等于5！\n");\n return 0;\n }\n\n Graph* graph = createGraph(numCities);\n MatrixGraph* matrixGraph = createMatrixGraph(numCities);\n\n printf("请依次输入城市之间的距离：\n");\n for (int i = 0; i < numCities; i++) {\n for (int j = i + 1; j < numCities; j++) {\n int distance;\n printf("城市 %d 到城市 %d 的距离：", i, j);\n scanf("%d", &distance);\n addEdge(graph, i, j, distance);\n addEdgeToMatrix(matrixGraph, i, j, distance);\n }\n }\n\n printGraph(graph);\n printMatrixGraph(matrixGraph);\n\n primMST(graph);\n kruskalMST(matrixGraph);\n\n return 0;\n}