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

#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX 100\n\ntypedef struct Edge {\n int src, dest, weight;\n} Edge;\n\ntypedef struct Graph {\n int V, E;\n Edge* edge;\n} Graph;\n\nGraph* createGraph(int V, int E) {\n Graph* graph = (Graph*)malloc(sizeof(Graph));\n graph->V = V;\n graph->E = E;\n graph->edge = (Edge*)malloc(E * sizeof(Edge));\n return graph;\n}\n\nvoid addEdge(Graph* graph, int src, int dest, int weight) {\n graph->edge[src].src = src;\n graph->edge[src].dest = dest;\n graph->edge[src].weight = weight;\n}\n\nvoid printMST(int parent[], int graph[MAX][MAX], int V) {\n printf("Minimum Spanning Tree with Adjacency Matrix:\n");\n printf("Edge \tWeight\n");\n for (int i = 1; i < V; i++) {\n printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);\n }\n}\n\nvoid primMST(int graph[MAX][MAX], int V) {\n int parent[MAX];\n int key[MAX];\n int mstSet[MAX];\n\n for (int i = 0; i < 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 < V - 1; count++) {\n int minKey = INT_MAX, minIndex;\n for (int v = 0; v < V; v++) {\n if (mstSet[v] == 0 && key[v] < minKey) {\n minKey = key[v];\n minIndex = v;\n }\n }\n\n mstSet[minIndex] = 1;\n\n for (int v = 0; v < V; v++) {\n if (graph[minIndex][v] && mstSet[v] == 0 && graph[minIndex][v] < key[v]) {\n parent[v] = minIndex;\n key[v] = graph[minIndex][v];\n }\n }\n }\n\n printMST(parent, graph, V);\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 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\nvoid kruskalMST(Graph* graph) {\n int V = graph->V;\n Edge result[V];\n int e = 0;\n int i = 0;\n\n qsort(graph->edge, graph->E, sizeof(graph->edge[0]), cmp);\n\n int parent[V];\n for (int v = 0; v < V; v++) {\n parent[v] = -1;\n }\n\n while (e < V - 1) {\n Edge next_edge = graph->edge[i++];\n\n int x = find(parent, next_edge.src);\n int y = find(parent, next_edge.dest);\n\n if (x != y) {\n result[e++] = next_edge;\n Union(parent, x, y);\n }\n }\n\n printf("\nMinimum Spanning Tree with Adjacency List:\n");\n printf("Edge \tWeight\n");\n for (i = 0; i < e; i++) {\n printf("%d - %d \t%d \n", result[i].src, result[i].dest, result[i].weight);\n }\n}\n\nint main() {\n int n;\n printf("Enter the number of cities (n >= 5): ");\n scanf("%d", &n);\n\n int graph[MAX][MAX];\n printf("Enter the distances between cities:\n");\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n scanf("%d", &graph[i][j]);\n }\n }\n\n Graph* adjListGraph = createGraph(n, n * (n - 1) / 2);\n int index = 0;\n for (int i = 0; i < n-1; i++) {\n for (int j = i+1; j < n; j++) {\n addEdge(adjListGraph, index, i, j, graph[i][j]);\n index++;\n }\n }\n\n printf("\nUsing Prim's Algorithm:\n");\n primMST(graph, n);\n\n printf("\nUsing Kruskal's Algorithm:\n");\n kruskalMST(adjListGraph);\n\n return 0;\n}\n