C语言实现城市网络建设最经济方案 - 邻接表、邻接矩阵、普利姆算法、克鲁斯卡尔算法

#include <stdio.h>\n#include <stdlib.h>\n#include <stdbool.h>\n\n// 定义最大城市数量\n#define MAX_CITY 10\n\n// 邻接表节点结构\ntypedef struct Node {\n int dest;\n int weight;\n struct Node* next;\n} Node;\n\n// 邻接表头结点结构\ntypedef struct HeadNode {\n Node* head;\n} HeadNode;\n\n// 邻接矩阵结构\ntypedef struct {\n int** matrix;\n int num;\n} Matrix;\n\n// 创建邻接表头结点\nHeadNode* createHeadNode() {\n HeadNode* headNode = (HeadNode*)malloc(sizeof(HeadNode));\n headNode->head = NULL;\n return headNode;\n}\n\n// 创建邻接表节点\nNode* createNode(int dest, int weight) {\n Node* newNode = (Node*)malloc(sizeof(Node));\n newNode->dest = dest;\n newNode->weight = weight;\n newNode->next = NULL;\n return newNode;\n}\n\n// 添加邻接表节点到头结点\nvoid addNode(HeadNode* headNode, int dest, int weight) {\n Node* newNode = createNode(dest, weight);\n newNode->next = headNode->head;\n headNode->head = newNode;\n}\n\n// 创建邻接表\nHeadNode** createAdjList(int num) {\n HeadNode** adjList = (HeadNode**)malloc(num * sizeof(HeadNode*));\n for (int i = 0; i < num; i++) {\n adjList[i] = createHeadNode();\n }\n return adjList;\n}\n\n// 添加边到邻接表\nvoid addEdgeToAdjList(HeadNode** adjList, int src, int dest, int weight) {\n addNode(adjList[src], dest, weight);\n addNode(adjList[dest], src, weight);\n}\n\n// 打印邻接表\nvoid printAdjList(HeadNode** adjList, int num) {\n for (int i = 0; i < num; i++) {\n Node* currNode = adjList[i]->head;\n printf("城市 %d 的邻接城市: ", i);\n while (currNode != NULL) {\n printf("%d ", currNode->dest);\n currNode = currNode->next;\n }\n printf("\n");\n }\n}\n\n// 创建邻接矩阵\nMatrix* createAdjMatrix(int num) {\n Matrix* adjMatrix = (Matrix*)malloc(sizeof(Matrix));\n adjMatrix->matrix = (int**)malloc(num * sizeof(int*));\n for (int i = 0; i < num; i++) {\n adjMatrix->matrix[i] = (int*)calloc(num, sizeof(int));\n }\n adjMatrix->num = num;\n return adjMatrix;\n}\n\n// 添加边到邻接矩阵\nvoid addEdgeToAdjMatrix(Matrix* adjMatrix, int src, int dest, int weight) {\n adjMatrix->matrix[src][dest] = weight;\n adjMatrix->matrix[dest][src] = weight;\n}\n\n// 打印邻接矩阵\nvoid printAdjMatrix(Matrix* adjMatrix) {\n printf("邻接矩阵:\n");\n for (int i = 0; i < adjMatrix->num; i++) {\n for (int j = 0; j < adjMatrix->num; j++) {\n printf("%d ", adjMatrix->matrix[i][j]);\n }\n printf("\n");\n }\n}\n\n// 获取最小权重的边的起点\nint getMinWeightEdge(int* weight, bool* visited, int num) {\n int minWeight = INT_MAX;\n int minIndex = -1;\n for (int i = 0; i < num; i++) {\n if (!visited[i] && weight[i] < minWeight) {\n minWeight = weight[i];\n minIndex = i;\n }\n }\n return minIndex;\n}\n\n// Prim算法生成最小生成树\nvoid primMST(HeadNode** adjList, int num) {\n int* parent = (int*)malloc(num * sizeof(int));\n int* weight = (int*)malloc(num * sizeof(int));\n bool* visited = (bool*)calloc(num, sizeof(bool));\n for (int i = 0; i < num; i++) {\n weight[i] = INT_MAX;\n }\n weight[0] = 0;\n parent[0] = -1;\n for (int i = 0; i < num - 1; i++) {\n int u = getMinWeightEdge(weight, visited, num);\n visited[u] = true;\n Node* currNode = adjList[u]->head;\n while (currNode != NULL) {\n int v = currNode->dest;\n int w = currNode->weight;\n if (!visited[v] && w < weight[v]) {\n parent[v] = u;\n weight[v] = w;\n }\n currNode = currNode->next;\n }\n }\n printf("\nPrim算法生成的最小生成树:\n");\n printf("边 权重\n");\n for (int i = 1; i < num; i++) {\n printf("%d - %d %d\n", parent[i], i, weight[i]);\n }\n}\n\n// Kruskal算法生成最小生成树\ntypedef struct {\n int src;\n int dest;\n int weight;\n} Edge;\n\nint compare(const void* a, const void* b) {\n return ((Edge*)a)->weight - ((Edge*)b)->weight;\n}\n\nint find(int* parent, int i) {\n if (parent[i] == -1)\n return i;\n return find(parent, parent[i]);\n}\n\nvoid unionSet(int* parent, int x, int y) {\n int xset = find(parent, x);\n int yset = find(parent, y);\n parent[xset] = yset;\n}\n\nvoid kruskalMST(Edge* edges, int num, int edgeNum) {\n int* parent = (int*)malloc(num * sizeof(int));\n memset(parent, -1, num * sizeof(int));\n qsort(edges, edgeNum, sizeof(Edge), compare);\n printf("\nKruskal算法生成的最小生成树:\n");\n printf("边 权重\n");\n for (int i = 0; i < edgeNum; i++) {\n int src = edges[i].src;\n int dest = edges[i].dest;\n int weight = edges[i].weight;\n int x = find(parent, src);\n int y = find(parent, dest);\n if (x != y) {\n printf("%d - %d %d\n", src, dest, weight);\n unionSet(parent, x, y);\n }\n }\n}\n\nint main() {\n int num;\n printf("请输入城市数量（>= 5）: ");\n scanf("%d", &num);\n if (num < 5) {\n printf("城市数量不得小于5。\n");\n return 0;\n }\n \n HeadNode** adjList = createAdjList(num);\n Matrix* adjMatrix = createAdjMatrix(num);\n Edge* edges = (Edge*)malloc((num * (num - 1) / 2) * sizeof(Edge));\n int edgeNum = 0;\n \n printf("请输入各城市之间的距离(用空格分隔):\n");\n for (int i = 0; i < num; i++) {\n for (int j = i + 1; j < num; j++) {\n int weight;\n printf("城市 %d 到城市 %d 的距离: ", i, j);\n scanf("%d", &weight);\n addEdgeToAdjList(adjList, i, j, weight);\n addEdgeToAdjMatrix(adjMatrix, i, j, weight);\n edges[edgeNum].src = i;\n edges[edgeNum].dest = j;\n edges[edgeNum].weight = weight;\n edgeNum++;\n }\n }\n \n printf("\n邻接表:\n");\n printAdjList(adjList, num);\n \n printf("\n邻接矩阵:\n");\n printAdjMatrix(adjMatrix);\n \n primMST(adjList, num);\n \n kruskalMST(edges, num, edgeNum);\n \n return 0;\n