本文为数据结构与算法课设-《最小生成树问题》课题的一个分享与讨论。采用树和图的数据结构。数据存储采用邻接矩阵。
1.设计内容和要求
| 设计内容： 在n个城市（n>=5）之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性。 |
2.实现思路和程序调试
程序就是在输入数据到一个邻接矩阵中，然后根据两种算法去输出最小生成树。
（1）prim 算法
Prim算法是一种用于在加权无向图中找到最小生成树的贪心算法。最小生成树是图中的一个子图，它包含了图中所有顶点，并且边的权重和最小。Prim算法从一个顶点开始，逐步增加边和顶点，直到形成最小生成树。
void prim(int graph[MAX][MAX], int n) { // 父节点数组，用于记录最小生成树中每个节点的父节点 int parent[MAX]; // key数组用于存储从源点到每个顶点的当前最小距离估计 int key[MAX]; // mstSet用于标记顶点是否已经被包括在最小生成树中 bool mstSet[MAX]; // 初始化所有距离为无穷大，并标记所有顶点都未被包括在MST中 for (int i = 0; i < n; i++) { key[i] = INT_MAX; // 假设所有距离都是无穷大 mstSet[i] = false; // 标记所有顶点都未被选中 } // 将第一个顶点加入到MST中，并将其距离设置为0（因为它到自身的距离是0） key[0] = 0; parent[0] = -1; // 第一个顶点没有父节点 // 重复n-1次，每次找到一个新的顶点加入到MST中 for (int count = 0; count < n - 1; count++) { // 寻找当前未被包括在MST中，且距离源点最近的顶点u int u = -1; for (int v = 0; v < n; v++) { if (!mstSet[v] && (u == -1 || key[v] < key[u])) { u = v; } } // 将顶点u加入到MST中 mstSet[u] = true; // 更新与顶点u相邻的顶点的距离估计 for (int v = 0; v < n; v++) { // 如果顶点v未被包括在MST中，并且存在一条从u到v的边，且这条边的权重小于v当前的key值 if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) { parent[v] = u; // 更新v的父节点为u key[v] = graph[u][v]; // 更新v的key值为u到v的权重 } } } // 打印最小生成树中的边 printf("使用 Prim 算法的最小生成树中的边：\n"); for (int i = 1; i < n; i++) { printf("%d - %d\n", parent[i], i); }
}Prim算法的关键在于逐步构建最小生成树，每次选择一个与当前MST中顶点集距离最小的顶点，并将其加入到MST中。这个过程中，需要不断地更新与已选顶点集相邻的未选顶点的距离估计，以便在下一轮选择时能够找到距离最小的顶点。通过这种方式，Prim算法能够确保最终得到的树是所有可能树中权重和最小的。
（2）Kruskal算法
这段代码实现的是Kruskal算法，它是一种用于在加权无向图中找到最小生成树的算法。最小生成树是图中的一个子图，它包含了图中所有顶点，并且边的权重和最小。Kruskal算法通过逐步添加边来构建最小生成树，但每次添加边时都会检查是否会形成环。
// 查找根节点的函数，实现路径压缩
int find(int parent[], int i) { if (parent[i] != i) { parent[i] = find(parent, parent[i]); // 路径压缩，将路径上的所有节点都直接指向根节点 } return parent[i];
} // 合并两个集合，按秩合并（根据树的深度或节点数来合并）
void unionSet(int parent[], int rank[], int x, int y) { int xroot = find(parent, x); int yroot = find(