C语言实现Kruskal和Prim最小生成树算法

#include <stdio.h>\n#include <stdlib.h>\n#include <stdbool.h>\n#include <time.h>\n#define MAX_VERTEX_NUM 100\n#define INFINITY 0x3f3f3f3f\n\ntypedef struct {\n int start, end;\n int weight;\n} Edge;\n\ntypedef struct {\n int vexnum, arcnum;\n int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];\n} MGraph;\n\n// 交换两个边的位置\nvoid Swap(Edge edges[], int i, int j) {\n Edge temp = edges[i];\n edges[i] = edges[j];\n edges[j] = temp;\n}\n\n// 快速排序\nvoid QuickSort(Edge edges[], int low, int high) {\n if (low < high) {\n int i = low, j = high;\n Edge pivot = edges[low];\n while (i < j) {\n while (i < j && edges[j].weight >= pivot.weight) {\n j--;\n }\n edges[i] = edges[j];\n while (i < j && edges[i].weight <= pivot.weight) {\n i++;\n }\n edges[j] = edges[i];\n }\n edges[i] = pivot;\n QuickSort(edges, low, i-1);\n QuickSort(edges, i+1, high);\n }\n}\n\n// 创建一个随机生成的带权无向图\nvoid CreateGraph(MGraph G) {\n int i, j, k;\n srand(time(NULL));\n printf("请输入图的顶点数和边数：");\n scanf("%d%d", &G->vexnum, &G->arcnum);\n for (i = 0; i < G->vexnum; i++) {\n for (j = 0; j < G->vexnum; j++) {\n G->edges[i][j] = INFINITY;\n }\n }\n printf("请输入边的起点、终点：\n");\n for (k = 0; k < G->arcnum; k++) {\n scanf("%d%d", &i, &j);\n if (i < 1 || i > G->vexnum || j < 1 || j > G->vexnum || i == j) {\n printf("边输入错误，请重新输入！\n");\n k--;\n continue;\n }\n if (G->edges[i-1][j-1] != INFINITY || G->edges[j-1][i-1] != INFINITY) {\n printf("边已经存在，请重新输入！\n");\n k--; \n continue;\n }\n G->edges[i-1][j-1] = G->edges[j-1][i-1] = rand() % 100 + 1; //权值生成在100以内\n }\n printf("随机生成的图的边及权值：\n");\n for (i = 0; i < G->vexnum; i++) {\n for (j = i+1; j < G->vexnum; j++) {\n if (G->edges[i][j] != INFINITY) {\n printf("(%d ,%d) : %d\n", i+1, j+1, G->edges[i][j]);\n }\n }\n }\n}\n\n// 判断顶点u和v是否在同一棵树中\nbool IsInTree(int parent[], int u, int v) {\n while (parent[u] >= 0) {\n u = parent[u];\n }\n while (parent[v] >= 0) {\n v = parent[v];\n }\n return u == v;\n}\n\n// Kruskal算法求最小生成树\nvoid Kruskal(MGraph G) {\n Edge edges[MAX_VERTEX_NUM(MAX_VERTEX_NUM-1)/2];\n int parent[MAX_VERTEX_NUM];\n int i, j, k = 0, cost = 0;\n // 将边存入edges数组中\n for (i = 0; i < G.vexnum; i++) {\n for (j = i+1; j < G.vexnum; j++) {\n if (G.edges[i][j] != INFINITY) {\n edges[k].start = i;\n edges[k].end = j;\n edges[k].weight = G.edges[i][j];\n k++;\n }\n }\n }\n // 对边按权值升序排序\n QuickSort(edges, 0, k-1);\n // 初始化parent数组，负数表示该结点为树的根结点，绝对值表示该结点的父结点\n for (i = 0; i < G.vexnum; i++) {\n parent[i] = -1;\n }\n // 逐条取出边，加入生成树中\n for (i = 0; i < k; i++) {\n if (!IsInTree(parent, edges[i].start, edges[i].end)) {\n printf("(%d ,%d) : %d\n", edges[i].start+1, edges[i].end+1, edges[i].weight);\n cost += edges[i].weight;\n // 将边的两个顶点加入同一棵树中\n int root1 = edges[i].start;\n int root2 = edges[i].end;\n while (parent[root1] >= 0) {\n root1 = parent[root1];\n }\n while (parent[root2] >= 0) {\n root2 = parent[root2];\n }\n parent[root1] += parent[root2];\n parent[root2] = root1;\n }\n }\n printf("最小生成树的代价为：%d\n", cost);\n}\n\n// Prim算法求最小生成树\nvoid Prim(MGraph G) {\n int lowcost[MAX_VERTEX_NUM];\n int closest[MAX_VERTEX_NUM];\n bool visited[MAX_VERTEX_NUM];\n int i, j, k, min, cost = 0;\n // 初始化lowcost和closest数组\n for (i = 1; i < G.vexnum; i++) {\n lowcost[i] = G.edges[0][i];\n closest[i] = 0;\n visited[i] = false;\n }\n visited[0] = true;\n // 逐个确定顶点，加入生成树中\n for (i = 1; i < G.vexnum; i++) {\n min = INFINITY;\n k = 0;\n // 选出最小的边\n for (j = 1; j < G.vexnum; j++) {\n if (!visited[j] && lowcost[j] < min) {\n min = lowcost[j];\n k = j;\n }\n }\n printf("(%d ,%d) : %d\n", closest[k]+1, k+1, min);\n visited[k] = true;\n cost += min;\n // 更新lowcost和closest数组\n for (j = 1; j < G.vexnum; j++) {\n if (!visited[j] && G.edges[k][j] < lowcost[j]) {\n lowcost[j] = G.edges[k][j];\n closest[j] = k;\n }\n }\n }\n printf("最小生成树的代价为：%d\n", cost);\n}\n\nint main() {\n MGraph G;\n CreateGraph(&G);\n printf("Kruskal算法求最小生成树：\n");\n Kruskal(G);\n printf("Prim算法求最小生成树：\n");\n Prim(G);\n return 0;\n}