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

#include\ <stdio.h>\n#include\ <stdlib.h>\n#include\ <limits.h>\n\n#define\ MAX_CITY\ 100\n\n//\ 邻接表结点\n\typedef\ struct\ Node\ {\n\ \ \ int\ city;\ \ \ //\ 目标城市\n\ \ \ int\ weight;\ \ \ //\ 距离\n\ \ \ struct\ Node\ *next;\ \ \ //\ 下一个邻接点\n} Node;\n\n//\ 邻接表\n\typedef\ struct\ AdjList\ {\n\ \ \ Node\ *head;\ \ \ //\ 邻接表头指针\n} AdjList;\n\n//\ 邻接矩阵\n\typedef\ struct\ AdjMatrix\ {\n\ \ \ int\ matrix[MAX_CITY][MAX_CITY];\ \ \ //\ 邻接矩阵\n} AdjMatrix;\n\n//\ 创建邻接表结点\n\Node\ *createNode(int\ city,\ int\ weight)\ {\n\ \ \ Node\ *newNode\ =\ (Node\ *)malloc(sizeof(Node));\n\ \ \ newNode->city\ =\ city;\n\ \ \ newNode->weight\ =\ weight;\n\ \ \ newNode->next\ =\ NULL;\n\ \ \ return\ newNode;\n}\n\n//\ 创建邻接表\n\AdjList\ *createAdjList()\ {\n\ \ \ AdjList\ *adjList\ =\ (AdjList\ *)malloc(sizeof(AdjList));\n\ \ \ adjList->head\ =\ NULL;\n\ \ \ return\ adjList;\n}\n\n//\ 添加边到邻接表\n\void\ addEdge(AdjList\ *adjList,\ int\ src,\ int\ dest,\ int\ weight)\ {\n\ \ \ Node\ *newNode\ =\ createNode(dest,\ weight);\n\ \ \ newNode->next\ =\ adjList->head;\n\ \ \ adjList->head\ =\ newNode;\n}\n\n//\ 创建邻接矩阵\n\AdjMatrix\ *createAdjMatrix(int\ n)\ {\n\ \ \ AdjMatrix\ *adjMatrix\ =\ (AdjMatrix\ *)malloc(sizeof(AdjMatrix));\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ for\ (int\ j\ =\ 0;\ j\ <\ n;\ j++)\ {\n\ \ \ \ \ \ \ adjMatrix->matrix[i][j]\ =\ 0;\n\ \ \ \ \ }\n\ \ \ }\n\ \ \ return\ adjMatrix;\n}\n\n//\ 添加边到邻接矩阵\n\void\ addEdgeMatrix(AdjMatrix\ *adjMatrix,\ int\ src,\ int\ dest,\ int\ weight)\ {\n\ \ \ adjMatrix->matrix[src][dest]\ =\ weight;\n\ \ \ adjMatrix->matrix[dest][src]\ =\ weight;\n}\n\n//\ 打印邻接表\n\void\ printAdjList(AdjList\ *adjList,\ int\ n)\ {\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ Node\ *temp\ =\ adjList[i].head;\n\ \ \ \ \ printf("城市\ %d\ 的邻接表:\ ",\ i);\n\ \ \ \ \ while\ (temp)\ {\n\ \ \ \ \ \ \ printf("->\ %d(%d)\ ",\ temp->city,\ temp->weight);\n\ \ \ \ \ \ \ temp\ =\ temp->next;\n\ \ \ \ \ }\n\ \ \ \ \ printf("\n");\n\ \ \ }\n}\n\n//\ 打印邻接矩阵\n\void\ printAdjMatrix(AdjMatrix\ *adjMatrix,\ int\ n)\ {\n\ \ \ printf("邻接矩阵:\n");\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ for\ (int\ j\ =\ 0;\ j\ <\ n;\ j++)\ {\n\ \ \ \ \ \ \ printf("%d\ ",\ adjMatrix->matrix[i][j]);\n\ \ \ \ \ }\n\ \ \ \ \ printf("\n");\n\ \ \ }\n}\n\n//\ 寻找最小生成树的下一个节点\n\int\ findNextNode(int\ *key,\ int\ *mstSet,\ int\ n)\ {\n\ \ \ int\ min\ =\ INT_MAX;\n\ \ \ int\ minIndex\ =\ -1;\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ if\ (mstSet[i]\ ==\ 0\ &&\ key[i]\ <\ min)\ {\n\ \ \ \ \ \ \ min\ =\ key[i];\n\ \ \ \ \ \ \ minIndex\ =\ i;\n\ \ \ \ \ }\n\ \ \ }\n\ \ \ return\ minIndex;\n}\n\n//\ 使用普利姆算法构建最小生成树\n\void\ prim(AdjList\ *adjList,\ int\ n)\ {\n\ \ \ int\ *parent\ =\ (int\ *)malloc(sizeof(int)\ *\ n);\ \ \ //\ 最小生成树的父节点\n\ \ \ int\ *key\ =\ (int\ *)malloc(sizeof(int)\ *\ n);\ \ \ //\ 用于选择下一个节点的键值\n\ \ \ int\ *mstSet\ =\ (int\ *)malloc(sizeof(int)\ *\ n);\ \ \ //\ 用于标记节点是否已加入最小生成树\n\n\ \ \ //\ 初始化键值和mstSet\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ 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\ <\ n\ -\ 1;\ count++)\ {\n\ \ \ \ \ int\ u\ =\ findNextNode(key,\ mstSet,\ n);\ \ \ //\ 选择下一个节点\n\ \ \ \ \ mstSet[u]\ =\ 1;\ \ \ //\ 标记节点已加入最小生成树\n\n\ \ \ \ \ //\ 更新键值和父节点\n\ \ \ \ \ Node\ *temp\ =\ adjList[u].head;\n\ \ \ \ \ while\ (temp)\ {\n\ \ \ \ \ \ \ int\ v\ =\ temp->city;\n\ \ \ \ \ \ \ int\ weight\ =\ temp->weight;\n\ \ \ \ \ \ \ if\ (mstSet[v]\ ==\ 0\ &&\ weight\ <\ key[v])\ {\n\ \ \ \ \ \ \ \ \ parent[v]\ =\ u;\n\ \ \ \ \ \ \ \ \ key[v]\ =\ weight;\n\ \ \ \ \ \ \ }\n\ \ \ \ \ \ \ temp\ =\ temp->next;\n\ \ \ \ \ }\n\ \ \ }\n\n\ \ \ //\ 打印最小生成树的节点和权值\n\ \ \ printf("\n使用普利姆算法构建的最小生成树:\n");\n\ \ \ for\ (int\ i\ =\ 1;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ printf("(%d,\ %d)\ -\ %d\n",\ parent[i],\ i,\ key[i]);\n\ \ \ }\n\n\ \ \ free(parent);\n\ \ \ free(key);\n\ \ \ free(mstSet);\n}\n\n//\ 使用克鲁斯卡尔算法构建最小生成树\n\void\ kruskal(AdjMatrix\ *adjMatrix,\ int\ n)\ {\n\ \ \ int\ *parent\ =\ (int\ *)malloc(sizeof(int)\ *\ n);\ \ \ //\ 最小生成树的父节点\n\ \ \ int\ *rank\ =\ (int\ *)malloc(sizeof(int)\ *\ n);\ \ \ //\ 用于判断是否形成环路的秩\n\ \ \ int\ edgeCount\ =\ 0;\ \ \ //\ 边的数量\n\ \ \ int\ *u\ =\ (int\ *)malloc(sizeof(int)\ *\ (n\ -\ 1));\ \ \ //\ 存储最小生成树的边\n\ \ \ int\ *v\ =\ (int\ *)malloc(sizeof(int)\ *\ (n\ -\ 1));\ \ \ //\ 存储最小生成树的边\n\ \ \ int\ *weight\ =\ (int\ *)malloc(sizeof(int)\ *\ (n\ -\ 1));\ \ \ //\ 存储最小生成树的边的权值\n\n\ \ \ //\ 初始化parent和rank\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ parent[i]\ =\ i;\n\ \ \ \ \ rank[i]\ =\ 0;\n\ \ \ }\n\n\ \ \ while\ (edgeCount\ <\ n\ -\ 1)\ {\n\ \ \ \ \ int\ min\ =\ INT_MAX;\n\ \ \ \ \ int\ a\ =\ -1,\ b\ =\ -1;\n\ \ \ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ \ \ for\ (int\ j\ =\ 0;\ j\ <\ n;\ j++)\ {\n\ \ \ \ \ \ \ \ \ if\ (adjMatrix->matrix[i][j]\ &&\ find(parent,\ i)\ !=\ find(parent,\ j)\ &&\ adjMatrix->matrix[i][j]\ <\ min)\ {\n\ \ \ \ \ \ \ \ \ \ \ min\ =\ adjMatrix->matrix[i][j];\n\ \ \ \ \ \ \ \ \ \ \ a\ =\ i;\n\ \ \ \ \ \ \ \ \ \ \ b\ =\ j;\n\ \ \ \ \ \ \ \ \ }\n\ \ \ \ \ \ \ }\n\ \ \ \ \ }\n\n\ \ \ \ \ unionSet(parent,\ rank,\ a,\ b);\n\ \ \ \ \ u[edgeCount]\ =\ a;\n\ \ \ \ \ v[edgeCount]\ =\ b;\n\ \ \ \ \ weight[edgeCount]\ =\ min;\n\ \ \ \ \ edgeCount++;\n\ \ \ }\n\n\ \ \ //\ 打印最小生成树的节点和权值\n\ \ \ printf("\n使用克鲁斯卡尔算法构建的最小生成树:\n");\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n\ -\ 1;\ i++)\ {\n\ \ \ \ \ printf("(%d,\ %d)\ -\ %d\n",\ u[i],\ v[i],\ weight[i]);\n\ \ \ }\n\n\ \ \ free(parent);\n\ \ \ free(rank);\n\ \ \ free(u);\n\ \ \ free(v);\n\ \ \ free(weight);\n}\n\n//\ 查找节点所属集合的根节点\n\int\ find(int\ *parent,\ int\ i)\ {\n\ \ \ if\ (parent[i]\ !=\ i)\ {\n\ \ \ \ \ parent[i]\ =\ find(parent,\ parent[i]);\n\ \ \ }\n\ \ \ return\ parent[i];\n}\n\n//\ 合并两个集合\n\void\ unionSet(int\ *parent,\ int\ *rank,\ int\ a,\ int\ b)\ {\n\ \ \ int\ rootA\ =\ find(parent,\ a);\n\ \ \ int\ rootB\ =\ find(parent,\ b);\n\ \ \ if\ (rank[rootA]\ <\ rank[rootB])\ {\n\ \ \ \ \ parent[rootA]\ =\ rootB;\n\ \ \ }\ else\ if\ (rank[rootA]\ >\ rank[rootB])\ {\n\ \ \ \ \ parent[rootB]\ =\ rootA;\n\ \ \ }\ else\ {\n\ \ \ \ \ parent[rootB]\ =\ rootA;\n\ \ \ \ \ rank[rootA]++;\n\ \ \ }\n}\n\n\int\ main()\ {\n\ \ \ int\ n;\n\ \ \ printf("请输入城市数n：");\n\ \ \ scanf("%d",\ &n);\n\n\ \ \ //\ 创建邻接表和邻接矩阵\n\ \ \ AdjList\ *adjList\ =\ (AdjList\ *)malloc(sizeof(AdjList)\ *\ n);\n\ \ \ AdjMatrix\ *adjMatrix\ =\ createAdjMatrix(n);\n\n\ \ \ //\ 手动录入城市之间的距离并存储\n\ \ \ printf("请按照城市之间的距离顺序依次输入距离（-1表示不相邻）：\n");\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ adjList[i].head\ =\ NULL;\n\ \ \ \ \ for\ (int\ j\ =\ 0;\ j\ <\ n;\ j++)\ {\n\ \ \ \ \ \ \ int\ distance;\n\ \ \ \ \ \ \ scanf("%d",\ &distance);\n\ \ \ \ \ \ \ if\ (distance\ !=\ -1)\ {\n\ \ \ \ \ \ \ \ \ addEdge(adjList\ +\ i,\ i,\ j,\ distance);\n\ \ \ \ \ \ \ \ \ addEdgeMatrix(adjMatrix,\ i,\ j,\ distance);\n\ \ \ \ \ \ \ }\n\ \ \ \ \ }\n\ \ \ }\n\n\ \ \ //\ 打印邻接表和邻接矩阵\n\ \ \ printAdjList(adjList,\ n);\n\ \ \ printAdjMatrix(adjMatrix,\ n);\n\n\ \ \ //\ 使用普利姆算法构建最小生成树\n\ \ \ prim(adjList,\ n);\n\n\ \ \ //\ 使用克鲁斯卡尔算法构建最小生成树\n\ \ \ kruskal(adjMatrix,\ n);\n\n\ \ \ //\ 释放内存\n\ \ \ for\ (int\ i\ =\ 0;\ i\ <\ n;\ i++)\ {\n\ \ \ \ \ Node\ *temp\ =\ adjList[i].head;\n\ \ \ \ \ while\ (temp)\ {\n\ \ \ \ \ \ \ Node\ *next\ =\ temp->next;\n\ \ \ \ \ \ \ free(temp);\n\ \ \ \ \ \ \ temp\ =\ next;\n\ \ \ \ \ }\n\ \ \ }\n\ \ \ free(adjList);\n\ \ \ free(adjMatrix);\n\n\ \ \ return\ 0;\n\