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; }

实验报告

实验目的：

熟悉Kruskal算法和Prim算法求解最小生成树的原理及流程。
掌握使用C语言实现Kruskal算法和Prim算法求解最小生成树的方法。

实验原理：

Kruskal算法：

将所有边按照权值从小到大进行排序。
依次选取权值最小的边，若该边的两个顶点不在同一颗树中，则将该边加入最小生成树中。
重复步骤2，直到最小生成树中的边数为顶点数减1。

Prim算法：

选择任意一个顶点作为起点。
从已选择的顶点集合中选取与其他顶点距离最近的顶点加入生成树中。
更新其他顶点到生成树的距离。
重复步骤2和3，直到生成树包含所有顶点。

实验步骤：

首先定义边的结构体Edge，包含起点、终点和权值。
定义图的结构体MGraph，包含顶点数、边数和邻接矩阵。
实现交换两个边的位置的Swap函数，用于快速排序。
实现快速排序函数QuickSort，用于对边按权值进行排序。
实现创建一个随机生成的带权无向图的函数CreateGraph，包括输入图的顶点数和边数，以及每条边的起点和终点，并随机生成权值。
实现判断顶点u和v是否在同一棵树中的函数IsInTree。
实现Kruskal算法求解最小生成树的函数Kruskal，包括将边存入数组中并排序，初始化parent数组，逐条取出边加入生成树中。
实现Prim算法求解最小生成树的函数Prim，包括初始化lowcost和closest数组，选取最小边加入生成树中，更新数组。
在主函数中调用CreateGraph函数创建图，然后依次调用Kruskal和Prim函数求解最小生成树。

实验结果：

根据输入的顶点数和边数，生成一个随机的带权无向图，输出边及权值。
使用Kruskal算法求解最小生成树，输出每条边及权值。
使用Prim算法求解最小生成树，输出每条边及权值。
输出最小生成树的代价。

实验结论：

通过实验可以发现，Kruskal算法和Prim算法都能够求解最小生成树，但是它们的实现方法略有不同。 Kruskal算法通过对边进行排序，然后逐条取出边加入生成树中，是一种贪心算法。 Prim算法通过选取已选择顶点集合中与其他顶点距离最近的顶点加入生成树中，不断更新顶点到生成树的距离，也是一种贪心算法。两种算法的时间复杂度都是O(n^2)，其中n为顶点数。