最小生成树(MST)
适用组别：提高组
难度系数：6
树的定理：N个结点用N-1条边连接成一个连通块，形成的图形只可能是树。
生成树的概念：
一个有N个结点的连通图，边一定是大于或等于N-1条边，在这些边中选择N-1条出来，连接所有的N个点， 称为生成树(spanning tree)。
生成树的特性：
1、包含连通图中所有的顶点；
2、任意两顶点之间有且仅有一条通路；
3、边数=顶点数-1
4、连通图的生成树不唯一
最小生成树：
如果这N-1条边的边权之和是所有方案中最小的，则称之为最小生成树(minimum spanning tree)。
最小生成树只在无向图中有，有向图没有最小生成树的概念。
一、最小生成树与最短路径树的区别
最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。
下图中，右下角的图就是橙色图的最小生成树
一、pirm算法
该算法从顶点的角度为出发点，时间复杂度为O(n2)，更适合与解决边的绸密度更高的连通网。是一种贪心算法。
具体代码实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | /**************************************************************** * Description: 使用 Prim 算法来实现最小生成树（MST） * Author: Alex Li * Date: 2024-01-31 04:01:34 * LastEditTime: 2024-01-31 04:15:02 ****************************************************************/ #include <iostream> using namespace std; // 定义图的顶点数 #define V 5 // 找到未包含在MST中、键值最小的顶点 int minKey(int key[], bool mstSet[]){ // 初始化最小值 int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (mstSet[v] == false && key[v] < min) min = key[v], min_index = v; return min_index; } // 打印构建的MST，它存储在parent[]数组中 void printMST(int parent[], int graph[V][V]){ cout << "Edge \tWeight\n"; for (int i = 1; i < V; i++) cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n"; } // 函数用于构造并打印由邻接矩阵表示的图的MST void primMST(int graph[V][V]){ int parent[V];// 存储构建的MST int key[V]; // 键值数组，用于选择最小权重边 bool mstSet[V]; // 表示已包含在MST中的顶点集合 // 初始化所有键值为无穷大 for (int i = 0; i < V; i++) key[i] = INT_MAX, mstSet[i] = false; // 总是将第一个顶点包含在MST中，将键值设置为0，使得该顶点成为第一个被选中的顶点 key[0] = 0; // 第一个节点总是MST的根 parent[0] = -1; // MST将有V个顶点 for (int count = 0; count < V - 1; count++) { // 从未包含在MST中的顶点集合中选出键值最小的顶点 int u = minKey(key, mstSet); // 将选出的顶点添加到MST集合中 mstSet[u] = true; // 更新相邻顶点的键值和父索引只考虑那些尚未包含在MST中的顶点 for (int v = 0; v < V; v++) // graph[u][v]仅对mstSet[v]为false的相邻顶点非零， 只有当graph[u][v]小于key[v]时，才更新键值 if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) parent[v] = u, key[v] = graph[u][v]; } // 打印构建的MST printMST(parent, graph); } // 主函数 int main() { // 图的邻接矩阵表示 int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // 打印解决方案 primMST(graph); return 0; } |
二、Kruskal算法
Kruskal算法，从边的角度求网的最小生成树，时间复杂度为O(eloge)。和prim算法恰恰相反，更适合于求边稀疏的网的最小生成树。
代码实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | /**************************************************************** * Description: C++ code to implement Kruskal's algorithm * Author: Alex Li * Date: 2023-05-17 09:53:47 * LastEditTime: 2024-01-31 04:54:05 ****************************************************************/ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1000; // 用于记录节点的集合，避免形成环路 int parent[N]; // n 为顶点数，m 为边的数量 int ans, n, m; struct Edge { // 存储边的权重 int head; int tail; int weight; } edge[N]; // 边的比较函数，用于排序 bool cmp(Edge a, Edge b){ return a.weight < b.weight; } void Kruscal(){ sort(edge, edge + m, cmp); // 对边进行排序 for (int i = 1; i <= n; i++) parent[i] = i; // 初始化各顶点的父节点 for (int i = 0; i < m; i++) { int pos1 = edge[i].head; int pos2 = edge[i].tail; // 检查两个顶点是否属于不同的集合，以避免环路的形成 if (parent[pos1] != parent[pos2]) { ans += edge[i].weight; // 将边的权重加到总和中 int maxx = max(parent[pos1], parent[pos2]); int minn = min(parent[pos1], parent[pos2]); // 将已选择的节点集合中较大编号统一更新为较小编号 for (int j = 1; j <= n; j++) { if (parent[j] == maxx) parent[j] = minn; } } } } int main(){ cin >> n >> m; for (int i = 0; i < m; i++) { // 输入边的信息 int u, v, w; // u 和 v 为顶点，w 为权重 cin >> u >> v >> w; // 输入边的相关信息 edge[i].head = u; edge[i].tail = v; edge[i].weight = w; // 将信息存储到结构体中 } Kruscal(); // 执行 Kruskal 算法 cout << ans; // 输出最小生成树的权重和 } |