门户网站是什么意思?,百度文库 旅游网站建设方案书,怎么安装网站源码,应届生求职网站官网文章目录 最小生成树概述 P r i m Prim Prim 算法 - 稠密图 - O ( n 2 ) O(n^2) O(n2)思路概述时间复杂度分析AcWing 858. Prim算法求最小生成树CODE K r u s k a l Kruskal Kruskal 算法 - 稀疏图 - O ( m l o g m ) O(mlogm) O(mlogm)思路解析时间复杂度分析AcWing 859. Kr… 文章目录 最小生成树概述 P r i m Prim Prim 算法 - 稠密图 - O ( n 2 ) O(n^2) O(n2)思路概述时间复杂度分析AcWing 858. Prim算法求最小生成树CODE K r u s k a l Kruskal Kruskal 算法 - 稀疏图 - O ( m l o g m ) O(mlogm) O(mlogm)思路解析时间复杂度分析AcWing 859. Kruskal算法求最小生成树CODE 最小生成树概述 P r i m Prim Prim 算法 - 稠密图 - O ( n 2 ) O(n^2) O(n2)
思路概述
跟 D i j k s t r a Dijkstra Dijkstra 算法很相近都是每个点轮一遍然后贪心找最小值同样 P r i m Prim Prim 也可以用堆优化但是不如 K r u s k a l Kruskal Kruskal 算法所以不用。
用到三个数组g[][]邻接矩阵存边st[]用于标记那些节点在生成树中dist[]存储每个节点到生成树的最小距离。首先初始化每个点到生成树的距离在一开始除了根节点是 0 0 0其他都是 I N F INF INF;然后每个点轮一遍因为生成树要每个点都在 再次遍历寻找到生成树最小的边连接的点如果遍历完了发现最小值是 I N F INF INF说明这个图不联通没有最小生成树。将这个点更新到生成树里去累计生成树的边长然后用这个点的值再更新一遍dist[]数组。 时间复杂度分析
外层循环 n n n 次内层是 2 n 2n 2n 次所以是 O ( n ⋅ 2 n ) O(n·2n) O(n⋅2n)也就是 O ( n 2 ) O(n^2) O(n2) AcWing 858. Prim算法求最小生成树
题目链接https://www.acwing.com/activity/content/problem/content/924/。 CODE
#include iostream // 引入输入输出流库
#include cstring // 引入字符串处理库
#include algorithm // 引入算法库using namespace std; // 使用标准命名空间const int N 520, INF 0x3f3f3f3f; // 定义常量N和INF
int g[N][N]; // 定义邻接矩阵g
int dist[N]; // 定义距离数组dist
bool st[N]; // 定义状态数组st
int n, m; // 定义顶点数n和边数mint prim(){ // 定义prim算法函数memset(dist, 0x3f, sizeof dist); // 初始化dist数组dist[1] 0; // 将起点的距离设为0int res 0; // 初始化结果resfor(int i 0; i n; i){ // 遍历所有顶点int t -1; // 初始化tfor(int j 1; j n; j) // 遍历所有顶点if(!st[j] (t -1 || dist[t] dist[j])) // 找到未被访问且距离最小的顶点t j;if(dist[t] INF) return INF; // 如果找不到顶点返回INFres dist[t]; // 更新结果st[t] true; // 标记顶点t已被访问for(int j 1; j n; j) dist[j] min(dist[j], g[j][t]); // 更新距离}return res; // 返回结果
}int main() // 主函数
{memset(g, 0x3f, sizeof g); // 初始化邻接矩阵gcin n m; // 输入顶点数和边数while (m -- ){ // 遍历所有边int a, b, c;scanf(%d%d%d, a, b, c); // 输入边的两个顶点和权值g[a][b] g[b][a] min(g[a][b], c); // 更新邻接矩阵}int t prim(); // 调用prim算法if(t INF) puts(impossible); // 如果返回INF输出impossibleelse printf(%d\n, t); // 否则输出结果
} K r u s k a l Kruskal Kruskal 算法 - 稀疏图 - O ( m l o g m ) O(mlogm) O(mlogm)
思路解析
首先将所有边按权值排序这一步是 K r u s k a l Kruskal Kruskal 的瓶颈复杂度是 O ( m ⋅ l o g m ) O(m·logm) O(m⋅logm)接着初始化并查集再把排序好的边轮一遍。 如果边的两个点的根节点不是同一个两个节点没有全在树中那就将两个点连起来然后节点数和权重累积。 最后判断如果生成树的边不是 n − 1 n - 1 n−1 条的话说明图不联通没有最小生成树。 时间复杂度分析
由上知排序瓶颈复杂度然后是后面遍历每一条边的复杂度 O ( m ) O(m) O(m)最后累计就是 O ( m l o g m ) O(mlogm) O(mlogm) 但是由于排序的常数很小所以实际运行时间比公式算出来要少的多。 AcWing 859. Kruskal算法求最小生成树
题目链接https://www.acwing.com/activity/content/problem/content/925/ CODE
#include iostream // 引入输入输出流库
#include cstring // 引入字符串处理库
#include algorithm // 引入算法库using namespace std; // 使用标准命名空间const int N 1e5 10, M 2e5 10, INF 0x3f3f3f3f; // 定义常量N、M和INF
int n, m; // 定义顶点数n和边数m
int p[N]; // 定义并查集数组pstruct edge{ // 定义边的结构体int a, b, w;
}edges[M];int find(int x){ // 定义并查集的查找函数if(x ! p[x]) p[x] find(p[x]);return p[x];
}bool cmp(edge a, edge b){ // 定义比较函数用于排序return a.w b.w;
}int kruskal(){ // 定义kruskal算法函数sort(edges, edges m, cmp); // 对所有边按权值进行排序for(int i 1; i n; i) p[i] i; // 初始化并查集int res 0, cnt 0; // 初始化结果res和计数器cntfor(int i 0; i m; i){ // 遍历所有边int a find(edges[i].a), b find(edges[i].b), w edges[i].w; // 找到边的两个顶点的根节点和权值if(a ! b){ // 如果两个顶点不在同一个集合中p[a] b; // 合并两个集合cnt; // 计数器加1res w; // 更新结果}}if(cnt n - 1) return INF; // 如果生成树的边数小于n-1返回INFelse return res; // 否则返回结果
}int main() // 主函数
{cin n m; // 输入顶点数和边数for(int i 0; i m; i){ // 遍历所有边int a, b, w;scanf(%d%d%d, a, b, w); // 输入边的两个顶点和权值edges[i] {a, b, w}; // 存储边}int t kruskal(); // 调用kruskal算法if(t INF) puts(impossible); // 如果返回INF输出impossibleelse printf(%d\n, t); // 否则输出结果
}
