法治中国建设网站,小程序推广怎么赚钱,设计师经常用的网站,网页设计素材有两种分别是什么文章目录 题目描述基本思路实现代码 题目描述
给定一个n个点m条边的无向图#xff0c;图中可能存在重边和自环#xff0c;边权可能为负数。求最小生成树的树边权重之和#xff0c;如果最小生成树不存在则输出impossible。 最小生成树的概念#xff1a;给定一张边带权的无向… 文章目录 题目描述基本思路实现代码 题目描述
给定一个n个点m条边的无向图图中可能存在重边和自环边权可能为负数。求最小生成树的树边权重之和如果最小生成树不存在则输出impossible。 最小生成树的概念给定一张边带权的无向图G(V,E)其中V表示图中点的集合E表示图中边的集合n|V|m|E|。由V中的全部n个顶点和E中n−1条边构成的无向连通子图被称为G的一棵生成树其中边的权值之和最小的生成树被称为无向图G的最小生成树。 输入格式
第一行包含两个整数n和m。接下来m行每行包含三个整数u,v,w表示点u和点v之间存在一条权值为w的边。
输出格式
共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出impossible。
数据范围
1 ≤ n ≤ 10^5,1 ≤ m ≤ 2×10^5,图中涉及边的边权的绝对值均不超过1000。
基本思路
读题获得的信息根据该图的点的个数n和边的条数m的取值范围可以判定该图是一个稀疏图。算法的基本流程和时间复杂度Kruskal算法的基本思路其实非常简单。将无向图中的所有边按照权重从小到大进行排序。这一步骤可以使用时间复杂度较低的排序算法如快速排序。在C中我们可以直接利用algorithm头文件中的sort函数来完成排序。值得注意的是这一步是Kruskal算法的性能瓶颈。当使用快速排序时其时间复杂度为O(mlogm)其中m是无向图中边的数量。快速排序的常数因子相对于其他同数量级时间复杂度的算法来说较小因此它具有较好的时间性能这也使得Kruskal算法在采用快速排序时表现出较高的效率。创建一个空的集合用于存储最终的边集。接着遍历无向图中的每一条边。对于每条边假设其起点编号为u终点编号为v权重为w。如果u和v不在同一个连通分量中则将该边加入到集合中并将u和v视为已连通。这里可以使用并查集这种数据结构来高效地实现这一过程。并查集的两个经典操作是连接两个元素和判断两个元素是否在同一个连通分量中。由于并查集每次操作的时间复杂度为O(α(n))其中α是阿克曼函数的反函数其增长非常缓慢几乎可以认为是常数时间因此处理所有边的时间复杂度接近O(m)。综上所述Kruskal算法的总时间复杂度为O(mlogm m) O(mlogm)。
实现代码
#include cstdio
#include algorithm
using namespace std;// 【辅助结构体定义】无向边结构体
struct undirectedEdge
{int u; // 第一个端点int v; // 第二个端点int w; // 边长权重
};
// 【辅助常量定义】记录无向图中点个数的上限
const int N 100010;// 【变量定义】无向图中点的个数和边的条数
int n, m;
// 【变量定义】每一条无向边的起点编号、终点编号和边长权重
int u, v, w;
// 【变量定义】记录无向图中每一条无向边的数组
undirectedEdge graph[2 * N];
// 【变量定义】并查集记录每一个元素所属的集合编号
int p[N];
// 【变量定义】记录最小生成树的权重之和
int result;
// 【变量定义】记录最小生成树中的边的数量
int edgeCount;// 【辅助函数定义】比较无向边的边长的函数用于后续无向边边长的升序排序
inline bool CompareByLength(const undirectedEdge e1, const undirectedEdge e2)
{return e1.w e2.w;
}
// 【辅助函数定义】用于查找和修改指定元素所属的集合编号的函数用于并查集
int find(int x)
{return x p[x] ? x : p[x] find(p[x]);
}int main(void)
{// 【变量输入】输入点的个数和无向边的条数scanf(%d%d, n, m);// 【变量输入】输入每一条无向边的起点编号、终点编号和边长权重for(int i 0; i m; i){scanf(%d%d%d, u, v, w);// 使用预先定义好的向量来存储无向边graph[i] {u, v, w};}// 【Krustal算法第一步】依据边长从小到大的顺序对无向边进行排序sort(graph, graph m, CompareByLength);// 【Krustal算法第二步】从小到大遍历无向边向量找出所有未连通的边将边的两个端点合并到一个集合中// 将并查集初始化让每个元素初始所属的集合编号就是其本身的编号for(int i 1; i n; i) p[i] i;for(int i 0; i m; i){// 首先找到u和v两个端点所属的集合int uRoot find(graph[i].u), vRoot find(graph[i].v);// 判定无向边的两个端点是否位于同一个集合中即是否连通如果不连通则修改为连通即加入同一个并查集if(uRoot ! vRoot){result graph[i].w; // 最小生成树权重之和增加 edgeCount; // 最小生成树边数增加p[uRoot] vRoot; // 修改两个端点之间的连通性}}// 【Krustal算法第三步】判定是否获得了最小生成树if(edgeCount n - 1) printf(impossible);else printf(%d, result);return 0;
}
