C语言实现城市网络最经济架设 - 普利姆和克鲁斯卡尔算法

#include <stdio.h>\n#include <stdlib.h>\n\n// 定义城市之间的距离结构体\ntypedef struct {\n int city1;\n int city2;\n int distance;\n} Distance;\n\n// 定义邻接表结点\ntypedef struct AdjListNode {\n int dest;\n int weight;\n struct AdjListNode* next;\n} AdjListNode;\n\n// 定义邻接表\ntypedef struct AdjList {\n AdjListNode* head;\n} AdjList;\n\n// 定义图结构\ntypedef struct Graph {\n int V; // 城市数\n AdjList* array;\n} Graph;\n\n// 创建节点\nAdjListNode* newAdjListNode(int dest, int weight) {\n AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));\n newNode->dest = dest;\n newNode->weight = weight;\n newNode->next = NULL;\n return newNode;\n}\n\n// 创建图\nGraph* createGraph(int V) {\n Graph* graph = (Graph*)malloc(sizeof(Graph));\n graph->V = V;\n graph->array = (AdjList*)malloc(V * sizeof(AdjList));\n for (int i = 0; i < V; ++i)\n graph->array[i].head = NULL;\n return graph;\n}\n\n// 添加边\nvoid addEdge(Graph* graph, int src, int dest, int weight) {\n AdjListNode* newNode = newAdjListNode(dest, weight);\n newNode->next = graph->array[src].head;\n graph->array[src].head = newNode;\n\n newNode = newAdjListNode(src, weight);\n newNode->next = graph->array[dest].head;\n graph->array[dest].head = newNode;\n}\n\n// 输出邻接表\nvoid printGraph(Graph* graph) {\n for (int i = 0; i < graph->V; ++i) {\n AdjListNode* pCrawl = graph->array[i].head;\n printf("城市 %d 的连接情况: ", i);\n while (pCrawl) {\n printf("-> %d(距离 %d) ", pCrawl->dest, pCrawl->weight);\n pCrawl = pCrawl->next;\n }\n printf("\n");\n }\n}\n\n// 普利姆算法\nvoid primMST(Graph* graph) {\n int parent[graph->V];\n int key[graph->V];\n int mstSet[graph->V];\n\n for (int i = 0; i < graph->V; ++i) {\n key[i] = INT_MAX;\n mstSet[i] = 0;\n }\n\n key[0] = 0;\n parent[0] = -1;\n\n for (int count = 0; count < graph->V - 1; ++count) {\n int u, min = INT_MAX;\n for (int v = 0; v < graph->V; ++v) {\n if (mstSet[v] == 0 && key[v] < min) {\n min = key[v];\n u = v;\n }\n }\n\n mstSet[u] = 1;\n\n AdjListNode* pCrawl = graph->array[u].head;\n while (pCrawl) {\n int v = pCrawl->dest;\n int weight = pCrawl->weight;\n if (mstSet[v] == 0 && weight < key[v]) {\n parent[v] = u;\n key[v] = weight;\n }\n pCrawl = pCrawl->next;\n }\n }\n\n printf("\n最小生成树:\n");\n printf("节点 权值\n");\n for (int i = 1; i < graph->V; ++i)\n printf("%d - %d %d\n", parent[i], i, key[i]);\n}\n\n// 克鲁斯卡尔算法\n\n// 按照距离升序排序边\nint compare(const void* a, const void* b) {\n return ((Distance)a).distance - ((Distance)b).distance;\n}\n\n// 查找顶点的父节点\nint find(int parent[], int i) {\n if (parent[i] == -1)\n return i;\n return find(parent, parent[i]);\n}\n\n// 合并两个集合\nvoid Union(int parent[], int x, int y) {\n int xset = find(parent, x);\n int yset = find(parent, y);\n parent[xset] = yset;\n}\n\n// 克鲁斯卡尔算法\nvoid kruskalMST(Distance dist[], int V, int E) {\n int parent[V];\n for (int i = 0; i < V; ++i)\n parent[i] = -1;\n\n int count = 0;\n int i = 0;\n\n while (count < V - 1) {\n int city1 = dist[i].city1;\n int city2 = dist[i].city2;\n int distance = dist[i].distance;\n\n int x = find(parent, city1);\n int y = find(parent, city2);\n\n if (x != y) {\n printf("%d - %d %d\n", city1, city2, distance);\n Union(parent, x, y);\n count++;\n }\n\n i++;\n }\n}\n\nint main() {\n int n;\n printf("请输入城市数n：");\n scanf("%d", &n);\n\n // 创建邻接表图\n Graph* graph = createGraph(n);\n\n Distance dist[n * (n - 1) / 2];\n int index = 0;\n\n printf("请依次输入城市之间的距离：\n");\n for (int i = 0; i < n; ++i) {\n for (int j = i + 1; j < n; ++j) {\n int distance;\n printf("城市%d到城市%d的距离：", i, j);\n scanf("%d", &distance);\n dist[index].city1 = i;\n dist[index].city2 = j;\n dist[index].distance = distance;\n addEdge(graph, i, j, distance);\n index++;\n }\n }\n\n printf("\n邻接表:\n");\n printGraph(graph);\n\n printf("\n普利姆算法:\n");\n primMST(graph);\n\n printf("\n克鲁斯卡尔算法:\n");\n qsort(dist, n * (n - 1) / 2, sizeof(Distance), compare);\n kruskalMST(dist, n, n * (n - 1) / 2);\n\n return 0;\n}