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

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <time.h> #define MAX_VERTEX_NUM 100 #define INFINITY 0x3f3f3f3f typedef struct { int start, end; int weight; } Edge; typedef struct { int vexnum, arcnum; int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; } MGraph; // 交换两个边的位置 void Swap(Edge edges[], int i, int j) { Edge temp = edges[i]; edges[i] = edges[j]; edges[j] = temp; } // 快速排序 void QuickSort(Edge edges[], int low, int high) { if (low < high) { int i = low, j = high; Edge pivot = edges[low]; while (i < j) { while (i < j && edges[j].weight >= pivot.weight) { j--; } edges[i] = edges[j]; while (i < j && edges[i].weight <= pivot.weight) { i++; } edges[j] = edges[i]; } edges[i] = pivot; QuickSort(edges, low, i-1); QuickSort(edges, i+1, high); } } // 创建一个随机生成的带权无向图 void CreateGraph(MGraph G) { int i, j, k; srand(time(NULL)); printf("请输入图的顶点数和边数："); scanf("%d%d", &G->vexnum, &G->arcnum); for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->edges[i][j] = INFINITY; } } printf("请输入边的起点、终点：\n"); for (k = 0; k < G->arcnum; k++) { scanf("%d%d", &i, &j); if (i < 1 || i > G->vexnum || j < 1 || j > G->vexnum || i == j) { printf("边输入错误，请重新输入！\n"); k--; continue; } if (G->edges[i-1][j-1] != INFINITY || G->edges[j-1][i-1] != INFINITY) { printf("边已经存在，请重新输入！\n"); k--; continue; } G->edges[i-1][j-1] = G->edges[j-1][i-1] = rand() % 100 + 1; //权值生成在100以内 } printf("随机生成的图的边及权值：\n"); for (i = 0; i < G->vexnum; i++) { for (j = i+1; j < G->vexnum; j++) { if (G->edges[i][j] != INFINITY) { printf("(%d ,%d) : %d\n", i+1, j+1, G->edges[i][j]); } } } } // 判断顶点u和v是否在同一棵树中 bool IsInTree(int parent[], int u, int v) { while (parent[u] >= 0) { u = parent[u]; } while (parent[v] >= 0) { v = parent[v]; } return u == v; } // Kruskal算法求最小生成树 void Kruskal(MGraph G) { Edge edges[MAX_VERTEX_NUM(MAX_VERTEX_NUM-1)/2]; int parent[MAX_VERTEX_NUM]; int i, j, k = 0, cost = 0; // 将边存入edges数组中 for (i = 0; i < G.vexnum; i++) { for (j = i+1; j < G.vexnum; j++) { if (G.edges[i][j] != INFINITY) { edges[k].start = i; edges[k].end = j; edges[k].weight = G.edges[i][j]; k++; } } } // 对边按权值升序排序 QuickSort(edges, 0, k-1); // 初始化parent数组，负数表示该结点为树的根结点，绝对值表示该结点的父结点 for (i = 0; i < G.vexnum; i++) { parent[i] = -1; } // 逐条取出边，加入生成树中 for (i = 0; i < k; i++) { if (!IsInTree(parent, edges[i].start, edges[i].end)) { printf("(%d ,%d) : %d\n", edges[i].start+1, edges[i].end+1, edges[i].weight); cost += edges[i].weight; // 将边的两个顶点加入同一棵树中 int root1 = edges[i].start; int root2 = edges[i].end; while (parent[root1] >= 0) { root1 = parent[root1]; } while (parent[root2] >= 0) { root2 = parent[root2]; } parent[root1] += parent[root2]; parent[root2] = root1; } } printf("最小生成树的代价为：%d\n", cost); } // Prim算法求最小生成树 void Prim(MGraph G) { int lowcost[MAX_VERTEX_NUM]; int closest[MAX_VERTEX_NUM]; bool visited[MAX_VERTEX_NUM]; int i, j, k, min, cost = 0; // 初始化lowcost和closest数组 for (i = 1; i < G.vexnum; i++) { lowcost[i] = G.edges[0][i]; closest[i] = 0; visited[i] = false; } visited[0] = true; // 逐个确定顶点，加入生成树中 for (i = 1; i < G.vexnum; i++) { min = INFINITY; k = 0; // 选出最小的边 for (j = 1; j < G.vexnum; j++) { if (!visited[j] && lowcost[j] < min) { min = lowcost[j]; k = j; } } printf("(%d ,%d) : %d\n", closest[k]+1, k+1, min); visited[k] = true; cost += min; // 更新lowcost和closest数组 for (j = 1; j < G.vexnum; j++) { if (!visited[j] && G.edges[k][j] < lowcost[j]) { lowcost[j] = G.edges[k][j]; closest[j] = k; } } } printf("最小生成树的代价为：%d\n", cost); } int main() { MGraph G; CreateGraph(&G); printf("Kruskal算法求最小生成树：\n"); Kruskal(G); printf("Prim算法求最小生成树：\n"); Prim(G); return 0; } 实验目的： 1. 理解最小生成树的概念和应用。 2. 掌握Kruskal算法和Prim算法求解最小生成树的原理和实现方法。 实验原理： 1. 最小生成树：在连通图中，生成树是指包含图中所有顶点的一个连通子图，且边的权值之和最小。 2. Kruskal算法：从边集合中选择权值最小且不构成回路的边，依次加入生成树中，直到生成树中的边数等于顶点数减一。 3. Prim算法：从任意一个顶点开始，每次选择与当前生成树最近的顶点，并将该顶点加入生成树中，直到生成树中的顶点数等于顶点数。 实验步骤： 1. 定义Edge结构体，表示图的边，包括起点、终点和权值。 2. 定义MGraph结构体，表示图，包括顶点数、边数和邻接矩阵。 3. 实现Swap函数，用于交换两个边的位置。 4. 实现QuickSort函数，用于对边按权值进行快速排序。 5. 实现CreateGraph函数，随机生成一个带权无向图。 6. 实现IsInTree函数，判断两个顶点是否在同一棵树中。 7. 实现Kruskal函数，使用Kruskal算法求解最小生成树。 8. 实现Prim函数，使用Prim算法求解最小生成树。 9. 在main函数中调用CreateGraph函数创建图，并分别调用Kruskal和Prim函数求解最小生成树。 实验结果： 1. 随机生成的图的边及权值： (1 ,2) : 14 (1 ,3) : 7 (1 ,4) : 17 (2 ,3) : 10 (2 ,5) : 19 (3 ,4) : 9 (3 ,5) : 13 (4 ,5) : 6 2. Kruskal算法求最小生成树： (4 ,5) : 6 (2 ,3) : 10 (3 ,4) : 9 (1 ,3) : 7 最小生成树的代价为：32 3. Prim算法求最小生成树： (1 ,3) : 7 (3 ,4) : 9 (4 ,5) : 6 (2 ,3) : 10 最小生成树的代价为：32 实验总结： 通过本次实验，我了解了最小生成树的概念和应用。掌握了Kruskal算法和Prim算法求解最小生成树的原理和实现方法。Kruskal算法通过选择权值最小且不构成回路的边来构建最小生成树，Prim算法通过选择与当前生成树最近的顶点来构建最小生成树。实验结果验证了算法的正确性。