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

#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_CITY 100\n\ntypedef struct Edge {\n int src, dest, weight;\n} Edge;\n\ntypedef struct Graph {\n int numCities;\n int numEdges;\n int matrix[MAX_CITY][MAX_CITY];\n Edge edges;\n} Graph;\n\nGraph createGraph(int numCities, int numEdges) {\n Graph graph = (Graph) malloc(sizeof(Graph));\n graph->numCities = numCities;\n graph->numEdges = numEdges;\n graph->edges = (Edge*) malloc(numEdges * sizeof(Edge));\n \n int i, j;\n for(i = 0; i < numCities; i++) {\n for(j = 0; j < numCities; j++) {\n graph->matrix[i][j] = 0;\n }\n }\n \n return graph;\n}\n\nvoid addEdge(Graph *graph, int src, int dest, int weight) {\n graph->matrix[src][dest] = weight;\n graph->matrix[dest][src] = weight;\n \n Edge edge;\n edge.src = src;\n edge.dest = dest;\n edge.weight = weight;\n \n graph->edges[src] = edge;\n graph->edges[dest] = edge;\n}\n\nvoid primMST(Graph *graph) {\n int selected[MAX_CITY];\n int parent[MAX_CITY];\n int min[MAX_CITY];\n \n int i, j;\n for(i = 0; i < graph->numCities; i++) {\n selected[i] = 0;\n min[i] = INT_MAX;\n }\n \n selected[0] = 1;\n parent[0] = -1;\n min[0] = 0;\n \n for(i = 0; i < graph->numCities - 1; i++) {\n int minIndex, minValue = INT_MAX;\n for(j = 0; j < graph->numCities; j++) {\n if(selected[j] == 0 && min[j] < minValue) {\n minValue = min[j];\n minIndex = j;\n }\n }\n \n selected[minIndex] = 1;\n \n for(j = 0; j < graph->numCities; j++) {\n if(graph->matrix[minIndex][j] != 0 && selected[j] == 0 && graph->matrix[minIndex][j] < min[j]) {\n parent[j] = minIndex;\n min[j] = graph->matrix[minIndex][j];\n }\n }\n }\n \n printf("Minimum Spanning Tree using Prim's Algorithm:\n");\n for(i = 1; i < graph->numCities; i++) {\n printf("%d - %d: %d\n", parent[i], i, graph->matrix[i][parent[i]]);\n }\n}\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(Graph *graph) {\n Edge result[MAX_CITY];\n \n qsort(graph->edges, graph->numEdges, sizeof(graph->edges[0]), compare);\n \n int parent[MAX_CITY];\n int i, j;\n for(i = 0; i < graph->numCities; i++) {\n parent[i] = -1;\n }\n \n int count = 0;\n i = 0;\n \n while(count < graph->numCities - 1) {\n Edge nextEdge = graph->edges[i++];\n \n int x = find(parent, nextEdge.src);\n int y = find(parent, nextEdge.dest);\n \n if(x != y) {\n result[count++] = nextEdge;\n unionSet(parent, x, y);\n }\n }\n \n printf("Minimum Spanning Tree using Kruskal's Algorithm:\n");\n for(i = 0; i < count; i++) {\n printf("%d - %d: %d\n", result[i].src, result[i].dest, result[i].weight);\n }\n}\n\nint main() {\n int numCities, numEdges;\n printf("Enter the number of cities: ");\n scanf("%d", &numCities);\n printf("Enter the number of edges: ");\n scanf("%d", &numEdges);\n \n Graph *graph = createGraph(numCities, numEdges);\n \n int i;\n for(i = 0; i < numEdges; i++) {\n int src, dest, weight;\n printf("Enter source, destination and weight of edge %d: ", i+1);\n scanf("%d %d %d", &src, &dest, &weight);\n addEdge(graph, src, dest, weight);\n }\n \n printf("\n");\n \n printf("Adjacency Matrix:\n");\n for(i = 0; i < numCities; i++) {\n for(int j = 0; j < numCities; j++) {\n printf("%d ", graph->matrix[i][j]);\n }\n printf("\n");\n }\n \n printf("\n");\n \n primMST(graph);\n \n printf("\n");\n \n kruskalMST(graph);\n \n return 0;\n}