质控中心网站建设申请,建立免费网站的步骤,3d建模软件免费下载,网页设计实训报告范文最小生成树
最小生成树:由n个节点#xff0c;和n-1条边构成的无向图被称为G的一棵生成树#xff0c;在G的所有生成树中#xff0c;边的权值之和最小的生成树#xff0c;被称为G的最小生成树。#xff08;换句话说就是用最小的代价把n个点都连起来#xff09;
Prim 算法…最小生成树
最小生成树:由n个节点和n-1条边构成的无向图被称为G的一棵生成树在G的所有生成树中边的权值之和最小的生成树被称为G的最小生成树。换句话说就是用最小的代价把n个点都连起来
Prim 算法普利姆 朴素版Prim(时间复杂度 O ( n 2 ) O(n^2) O(n2),适用于稠密图 堆优化版Prim(时间复杂度 O ( m l o g n ) O(m log n) O(mlogn),适用于稀疏图),基本不用 Kruskal算法适用于稀疏图时间复杂度 O ( m l o g m ) O(m log m) O(mlogm).$
如果是稠密图通常选用朴素版Prim算法因为其思路比较简洁代码比较短如果是稀疏图通常选用Kruskal算法因为其思路比Prim简单清晰。堆优化版的Prim通常不怎么用。
1.Prim
朴素Prim 与朴素dijkstra思想几乎一样只不过Prim算法的距离指得是点到最小生成树的集合的距离而Dijkstra算法的距离是点到起点的距离。适合用于稠密图 Prim 算法过程
初始化 dist 数组表示各点到最小生成树的距离。开始时设为无穷大INF。使用贪心策略每次选取距离集合最近的点 t并将其加入最小生成树。若该点距离 INF 且不是第一个节点表示图不连通直接返回 INF。更新其余未加入集合的点与最小生成树的最短距离。最终返回最小生成树的总权值若图不连通则输出 impossible。
实现思路
初始化各点到集合的距离INFn次循环每次找到集合外且距离集合最近的点t需要先判断除第一个点外找到的距离最近的点t距离是不是INF 若是则不存在最小生成树了结束否则还可能存在继续操作用该点t来更新其它点到集合的距离这里就是和Dijkstra最主要的区别然后将该点t加入集合 关于集合到距离最近的点实际上就是不在集合的点与集合内的点的各个距离的最小值每次加入新的点都会尝试更新一遍dist[j] min(dist[j],g[t][j]).在Dijkstra中是dist[j] - min(dits[j],dist[t] g[t][j]));
板子
const int N 510, INF 0x3f3f3f3f; // 定义最大节点数 N 和无穷大 INF
int g[N][N], dist[N]; // g[i][j] 表示从节点 i 到节点 j 的边权dist[i] 表示当前生成树到节点 i 的最短距离
bool st[N]; // st[i] 表示节点 i 是否已经加入到最小生成树中int n, m; // n 表示节点数量m 表示边的数量// 返回最小生成树的权值之和。如果图不连通返回 INF
int prim() {memset(dist, 0x3f, sizeof dist); // 初始化所有节点的最短距离为 INF即无穷大int res 0; // 最终的最小生成树权值之和// Prim 算法的核心循环 n 次每次找到一个未加入集合的最近节点for (int i 0; i n; i) {int t -1; // 用于记录当前找到的距离最小的节点// 找到距离当前生成树最近的未加入集合的节点for (int j 1; j n; j) {if (!st[j] (t -1 || dist[t] dist[j])) t j;}// 如果当前是第一个节点或者找到的节点距离集合为 INF说明图不连通if (i dist[t] INF) return INF; // 无法构成最小生成树if (i) res dist[t]; // 将该节点的边权值加入最终结果中// 更新其他未加入集合的节点到生成树的最短距离for (int j 1; j n; j) {dist[j] min(dist[j], g[t][j]); // 使用该节点 t 更新其他节点的最短距离}st[t] true; // 标记该节点已经加入生成树}return res; // 返回最小生成树的总权值
}Acwing 858.Prim 算法求最小生成树 注意本题干未设起点所以要迭代n次并且图中可能存在负的自环因此计算最小生成树的总距离要在更新各点到集合距离之前。且该图为无向图含重边则构建边需要注意。
具体实现代码详解版
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 510, INF 0x3f3f3f3f; // 定义最大节点数 N 和无穷大 INF
int g[N][N], dist[N]; // g[i][j] 表示从节点 i 到节点 j 的边权dist[i] 表示当前生成树到节点 i 的最短距离
bool st[N]; // st[i] 表示节点 i 是否已经加入到最小生成树中int n, m; // n 表示节点数量m 表示边的数量// 返回最小生成树的权值之和。如果图不连通返回 INF
int prim() {memset(dist, 0x3f, sizeof dist); // 初始化所有节点的最短距离为 INF即无穷大int res 0; // 最终的最小生成树权值之和// Prim 算法的核心循环 n 次每次找到一个未加入集合的最近节点for (int i 0; i n; i) {int t -1; // 用于记录当前找到的距离最小的节点// 找到距离当前生成树最近的未加入集合的节点for (int j 1; j n; j) {if (!st[j] (t -1 || dist[t] dist[j])) t j;}// 如果当前是第一个节点或者找到的节点距离集合为 INF说明图不连通if (i dist[t] INF) return INF; // 无法构成最小生成树if (i) res dist[t]; // 将该节点的边权值加入最终结果中// 更新其他未加入集合的节点到生成树的最短距离for (int j 1; j n; j) {dist[j] min(dist[j], g[t][j]); // 使用该节点 t 更新其他节点的最短距离}st[t] true; // 标记该节点已经加入生成树}return res; // 返回最小生成树的总权值
}int main() {cin n m; // 输入节点数 n 和边数 mmemset(g, 0x3f, sizeof g); // 初始化邻接矩阵所有边权值设为无穷大表示节点间无边// 输入每条边的信息构建邻接矩阵while (m--) {int a, b, c;cin a b c;g[a][b] g[b][a] min(g[a][b], c); // 无向图所以 g[a][b] 和 g[b][a] 相同}int t prim(); // 调用 Prim 算法计算最小生成树的权值// 输出结果。如果返回的是 INF说明图不连通输出 impossibleif (t INF) puts(impossible);else cout t endl; // 否则输出最小生成树的权值return 0;
}
堆优化Prim思路和堆优化的Dijkstra思路基本一样且基本不用对于稀疏图不如用Kruskal这里略过
2. Kruskal
适用于稀疏图时间复杂度 O ( m l o g m ) O(m log m) O(mlogm).Kruskal 算法是求解无向连通图的 最小生成树MST的经典算法。它的核心思想是通过贪心策略按权值从小到大逐步选择边确保不会产生环直到选出 n-1 条边为止。整个过程涉及使用 并查集 来判断是否形成环
先将所有的边按照权重从小到大排序从小到大枚举每条边a,b,w)若ab不连通则将这条边加入集合中(将a点和b点连接起来实质上是一个并查集的应用两点之间加边看两点是否存在一个连通块无需用邻接表、邻接矩阵存储图直接使用结构体表示边及其权值 板子
const int N 200010, INF 0x3f3f3f3f;
int p[N]; // 并查集的父节点数组
int n, m; // n 表示节点数m 表示边数// 边的结构体表示一条边及其权值
struct Edge {int a, b, w; // a, b 为连接的两个节点w 为权值// 重载小于运算符用于按边权值升序排序bool operator(const Edge W) const {return w W.w;}
} edges[N]; // 存储所有边// 并查集寻找节点 x 所在集合的根节点
int find(int x) {if (p[x] ! x) p[x] find(p[x]); // 路径压缩找到根节点并直接连接return p[x];
}// Kruskal 算法求最小生成树
int kruskal() {sort(edges, edges m); // 按照边的权值升序排序for (int i 1; i n; i) p[i] i; // 初始化并查集每个节点的父节点是自己int res 0, cnt 0; // res 存储最小生成树的权值之和cnt 记录最小生成树的边数// 遍历所有边for (int i 0; i m; i) {int a edges[i].a, b edges[i].b, w edges[i].w;// 找到两个节点的根节点a find(a), b find(b);if (a ! b) { // 如果两点不在同一个集合中说明它们不连通p[a] b; // 将两点所在的集合合并res w; // 累加这条边的权值cnt; // 增加计数}}// 如果使用的边数不足 n-1则说明图不连通无法构成最小生成树if (cnt n - 1) return INF;else return res; // 返回最小生成树的权值
}具体实现代码详解版
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 200010, INF 0x3f3f3f3f;
int p[N]; // 并查集的父节点数组
int n, m; // n 表示节点数m 表示边数// 边的结构体表示一条边及其权值
struct Edge {int a, b, w; // a, b 为连接的两个节点w 为权值// 重载小于运算符用于按边权值升序排序bool operator(const Edge W) const {return w W.w;}
} edges[N]; // 存储所有边// 并查集寻找节点 x 所在集合的根节点
int find(int x) {if (p[x] ! x) p[x] find(p[x]); // 路径压缩找到根节点并直接连接return p[x];
}// Kruskal 算法求最小生成树
int kruskal() {sort(edges, edges m); // 按照边的权值升序排序for (int i 1; i n; i) p[i] i; // 初始化并查集每个节点的父节点是自己int res 0, cnt 0; // res 存储最小生成树的权值之和cnt 记录最小生成树的边数// 遍历所有边for (int i 0; i m; i) {int a edges[i].a, b edges[i].b, w edges[i].w;// 找到两个节点的根节点a find(a), b find(b);if (a ! b) { // 如果两点不在同一个集合中说明它们不连通p[a] b; // 将两点所在的集合合并res w; // 累加这条边的权值cnt; // 增加计数}}// 如果使用的边数不足 n-1则说明图不连通无法构成最小生成树if (cnt n - 1) return INF;else return res; // 返回最小生成树的权值
}int main() {cin n m; // 输入节点数和边数for (int i 0; i m; i) {int a, b, w;cin a b w; // 输入每条边的两个端点 a, b 和边的权值 wedges[i] {a, b, w}; // 存储边的信息}int t kruskal(); // 调用 Kruskal 算法if (t INF) puts(impossible); // 如果返回值为 INF说明图不连通else cout t endl; // 否则输出最小生成树的权值return 0;
}
Kruskal 算法的核心思想
贪心策略每次选择权值最小的边且不形成环并查集用于快速检查两个节点是否已经连通以及合并不同的连通集合。
3.对比总结
