C语言实现城市网络构建：最小生成树算法（普利姆和克鲁斯卡尔）

{/'title/':/'C语言实现城市网络构建：最小生成树算法（普利姆和克鲁斯卡尔）/',/'description/':/'本文提供一个用C语言编写的代码，使用邻接矩阵和邻接表两种存储结构，实现最经济的城市网络构建。代码采用普利姆和克鲁斯卡尔算法寻找最小生成树，并输出最终结果。/',/'keywords/':/'C语言，最小生成树，普利姆算法，克鲁斯卡尔算法，城市网络，邻接矩阵，邻接表/',/'content/':/'#include <stdio.h>//n#include <stdlib.h>//n//n#define MAX_CITY 100//n//ntypedef struct {//n int city1;//n int city2;//n int distance;//n} Edge;//n//ntypedef struct {//n int vertex;//n int weight;//n} AdjNode;//n//ntypedef struct {//n int numCities;//n int numEdges;//n int adjMatrix[MAX_CITY][MAX_CITY];//n Edge edges[MAX_CITY];//n} Graph;//n//nGraph createGraph(int numCities) {//n Graph graph;//n graph.numCities = numCities;//n graph.numEdges = 0;//n for (int i = 0; i < numCities; i++) {//n for (int j = 0; j < numCities; j++) {//n graph.adjMatrix[i][j] = -1;//n }//n }//n return graph;//n}//n//nvoid addEdge(Graph *graph, int city1, int city2, int distance) {//n graph->edges[graph->numEdges].city1 = city1;//n graph->edges[graph->numEdges].city2 = city2;//n graph->edges[graph->numEdges].distance = distance;//n graph->adjMatrix[city1][city2] = distance;//n graph->adjMatrix[city2][city1] = distance;//n graph->numEdges++;//n}//n//nvoid printGraph(Graph graph) {//n printf(/'Adjacency Matrix://n/');//n for (int i = 0; i < graph.numCities; i++) {//n for (int j = 0; j < graph.numCities; j++) {//n printf(/'%d /', graph.adjMatrix[i][j]);//n }//n printf(/'//n/');//n }//n printf(/'//nEdges://n/');//n for (int i = 0; i < graph.numEdges; i++) {//n printf(/'%d - %d : %d//n/', graph.edges[i].city1, graph.edges[i].city2, graph.edges[i].distance);//n }//n}//n//nvoid primMST(Graph graph) {//n int selected[MAX_CITY];//n for (int i = 0; i < graph.numCities; i++) {//n selected[i] = 0;//n }//n selected[0] = 1;//n int numSelected = 1;//n //n printf(/'//nMinimum Spanning Tree (Prim's Algorithm)://n/');//n while (numSelected < graph.numCities) {//n int minDistance = -1;//n int minCity1, minCity2;//n //n for (int i = 0; i < graph.numCities; i++) {//n if (selected[i]) {//n for (int j = 0; j < graph.numCities; j++) {//n if (!selected[j] && graph.adjMatrix[i][j] != -1) {//n if (minDistance == -1 || graph.adjMatrix[i][j] < minDistance) {//n minDistance = graph.adjMatrix[i][j];//n minCity1 = i;//n minCity2 = j;//n }//n }//n }//n }//n }//n //n printf(/'%d - %d : %d//n/', minCity1, minCity2, minDistance);//n selected[minCity2] = 1;//n numSelected++;//n }//n}//n//nint findRoot(int *parent, int city) {//n while (parent[city] != -1) {//n city = parent[city];//n }//n return city;//n}//n//nvoid kruskalMST(Graph graph) {//n int parent[MAX_CITY];//n for (int i = 0; i < graph.numCities; i++) {//n parent[i] = -1;//n }//n //n Edge selectedEdges[MAX_CITY];//n int numSelected = 0;//n //n printf(/'//nMinimum Spanning Tree (Kruskal's Algorithm)://n/');//n while (numSelected < graph.numCities - 1) {//n int minDistance = -1;//n int minCity1, minCity2;//n //n for (int i = 0; i < graph.numEdges; i++) {//n int city1 = graph.edges[i].city1;//n int city2 = graph.edges[i].city2;//n int root1 = findRoot(parent, city1);//n int root2 = findRoot(parent, city2);//n if (root1 != root2) {//n if (minDistance == -1 || graph.edges[i].distance < minDistance) {//n minDistance = graph.edges[i].distance;//n minCity1 = city1;//n minCity2 = city2;//n }//n }//n }//n //n printf(/'%d - %d : %d//n/', minCity1, minCity2, minDistance);//n parent[minCity2] = minCity1;//n numSelected++;//n }//n}//n//nint main() {//n int numCities;//n printf(/'Enter the number of cities (>= 5): /');//n scanf(/'%d/', &numCities);//n //n if (numCities < 5) {//n printf(/'Invalid number of cities.//n/');//n return 0;//n }//n //n Graph graph = createGraph(numCities);//n //n printf(/'//nEnter the distances between cities://n/');//n for (int i = 0; i < numCities - 1; i++) {//n for (int j = i + 1; j < numCities; 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(/'//n/');//n printGraph(graph);//n //n primMST(graph);//n kruskalMST(graph);//n //n return 0;//n}/