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

#include <stdio.h>\n#include <stdlib.h>\n#include <stdbool.h>\n\n#define MAX_SIZE 100\n\n// 邻接表存储结构\ntypedef struct node {\n int vertex; // 目标城市\n int weight; // 距离\n struct node* next; // 下一个节点\n} Node;\n\ntypedef struct graph {\n int numVertices; // 城市数\n Node* adjLists[MAX_SIZE]; // 邻接表数组\n} Graph;\n\n// 创建节点\nNode* createNode(int v, int w) {\n Node* newNode = (Node*)malloc(sizeof(Node));\n newNode->vertex = v;\n newNode->weight = w;\n newNode->next = NULL;\n return newNode;\n}\n\n// 创建图\nGraph* createGraph(int vertices) {\n Graph* graph = (Graph*)malloc(sizeof(Graph));\n graph->numVertices = vertices;\n\n for (int i = 0; i < vertices; i++) {\n graph->adjLists[i] = NULL;\n }\n\n return graph;\n}\n\n// 添加边\nvoid addEdge(Graph* graph, int src, int dest, int weight) {\n Node* newNode = createNode(dest, weight);\n newNode->next = graph->adjLists[src];\n graph->adjLists[src] = newNode;\n\n newNode = createNode(src, weight);\n newNode->next = graph->adjLists[dest];\n graph->adjLists[dest] = newNode;\n}\n\n// 打印邻接表\nvoid printGraph(Graph* graph) {\n for (int i = 0; i < graph->numVertices; i++) {\n Node* temp = graph->adjLists[i];\n printf("Vertex %d: ", i);\n while (temp) {\n printf("(%d, %d) ", temp->vertex, temp->weight);\n temp = temp->next;\n }\n printf("\n");\n }\n}\n\n// 普利姆算法\nvoid primMST(Graph* graph) {\n int parent[MAX_SIZE]; // 最小生成树的父节点\n int key[MAX_SIZE]; // 顶点的键值\n bool mstSet[MAX_SIZE]; // 是否已被加入最小生成树\n\n // 初始化键值和mstSet\n for (int i = 0; i < graph->numVertices; i++) {\n key[i] = INT_MAX;\n mstSet[i] = false;\n }\n\n key[0] = 0; // 第一个顶点作为根节点\n parent[0] = -1; // 根节点没有父节点\n\n for (int count = 0; count < graph->numVertices - 1; count++) {\n int minKey = INT_MAX;\n int minIndex;\n\n // 找到键值最小的顶点\n for (int v = 0; v < graph->numVertices; v++) {\n if (mstSet[v] == false && key[v] < minKey) {\n minKey = key[v];\n minIndex = v;\n }\n }\n\n mstSet[minIndex] = true;\n\n // 更新相邻顶点的键值和父节点\n Node* temp = graph->adjLists[minIndex];\n while (temp) {\n int v = temp->vertex;\n int w = temp->weight;\n if (mstSet[v] == false && w < key[v]) {\n parent[v] = minIndex;\n key[v] = w;\n }\n temp = temp->next;\n }\n }\n\n printf("Minimum Spanning Tree using Prim's Algorithm:\n");\n for (int i = 1; i < graph->numVertices; i++) {\n printf("%d - %d\n", parent[i], i);\n }\n}\n\n// 克鲁斯卡尔算法\n\ntypedef struct edge {\n int src;\n int dest;\n int weight;\n} Edge;\n\ntypedef struct subset {\n int parent;\n int rank;\n} Subset;\n\nint find(Subset subsets[], int i) {\n if (subsets[i].parent != i) {\n subsets[i].parent = find(subsets, subsets[i].parent);\n }\n return subsets[i].parent;\n}\n\nvoid Union(Subset subsets[], int x, int y) {\n int xroot = find(subsets, x);\n int yroot = find(subsets, y);\n\n if (subsets[xroot].rank < subsets[yroot].rank) {\n subsets[xroot].parent = yroot;\n } else if (subsets[xroot].rank > subsets[yroot].rank) {\n subsets[yroot].parent = xroot;\n } else {\n subsets[yroot].parent = xroot;\n subsets[xroot].rank++;\n }\n}\n\nint compare(const void* a, const void* b) {\n return ((Edge*)a)->weight - ((Edge*)b)->weight;\n}\n\nvoid kruskalMST(Graph* graph) {\n Edge result[MAX_SIZE];\n int e = 0; // 结果数组的索引\n int i = 0; // 边的索引\n\n qsort(graph->edges, graph->numEdges, sizeof(Edge), compare);\n\n Subset* subsets = (Subset*)malloc(graph->numVertices * sizeof(Subset));\n\n for (int v = 0; v < graph->numVertices; v++) {\n subsets[v].parent = v;\n subsets[v].rank = 0;\n }\n\n while (e < graph->numVertices - 1 && i < graph->numEdges) {\n Edge next_edge = graph->edges[i++];\n\n int x = find(subsets, next_edge.src);\n int y = find(subsets, next_edge.dest);\n\n if (x != y) {\n result[e++] = next_edge;\n Union(subsets, x, y);\n }\n }\n\n printf("Minimum Spanning Tree using Kruskal's Algorithm:\n");\n for (int i = 0; i < e; i++) {\n printf("%d - %d\n", result[i].src, result[i].dest);\n }\n}\n\nint main() {\n int n;\n printf("Enter the number of cities (n >= 5): ");\n scanf("%d", &n);\n\n Graph* graph = createGraph(n);\n\n printf("Enter distances between cities:\n");\n for (int i = 0; i < n; i++) {\n for (int j = i + 1; j < n; j++) {\n int distance;\n printf("Distance between city %d and city %d: ", i, j);\n scanf("%d", &distance);\n addEdge(graph, i, j, distance);\n }\n }\n\n printf("\nAdjacency List:\n");\n printGraph(graph);\n\n primMST(graph);\n\n kruskalMST(graph);\n\n return 0;\n