当前位置: 首页 > news >正文

算法刷题笔记 Kruskal算法求最小生成树(详细算法介绍,详细注释C++代码实现)

文章目录

    • 题目描述
    • 基本思路
    • 实现代码

题目描述

  • 给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。
  • 求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible

最小生成树的概念:给定一张边带权的无向图G=(V,E),其中V表示图中点的集合,E表示图中边的集合,n=|V|m=|E|。由V中的全部n个顶点和En−1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入格式

  • 第一行包含两个整数nm
  • 接下来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。如果uv不在同一个连通分量中,则将该边加入到集合中,并将uv视为已连通。这里可以使用并查集这种数据结构来高效地实现这一过程。并查集的两个经典操作是:连接两个元素和判断两个元素是否在同一个连通分量中。由于并查集每次操作的时间复杂度为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;
}
http://www.lryc.cn/news/413983.html

相关文章:

  • 5年经验的软件测试人员,碰到这样的面试题居然会心虚......
  • C#进阶-轻量级ORM框架Dapper的使用教程与原理详解
  • Windows图形界面(GUI)-MFC-C/C++ - 编辑框(Edit Control) - CEdit
  • 网络安全防御【IPsec VPN搭建】
  • java环境配置与tomcat的配置
  • OD C卷 - 来自异国的客人/幸运数字
  • C++ | 动态内存管理 new、delete (用法、底层)详解
  • 【C语言】结构体内存布局解析——字节对齐
  • 模型表达方式
  • 校园课程助手【4】-使用Elasticsearch实现课程检索
  • 经典运维面试题
  • 别再盲目推广了!Xinstall助你开启App线下推广新篇章
  • 大厂linux面试题攻略五之数据库管理
  • 【pytorch】模型集成
  • 初识集合和数据结构
  • cocos creator 3.x中动态加载 resources 文件夹下的图片时提示找不到
  • 第九十八周周报
  • 程序员找工作之数据结构面试题总结分析
  • 设置provider解决maven找不到JUnit 5测试样例
  • php反序列化靶机serial实战
  • 类型推断技术及仓颉语言实践
  • 职场生存秘籍:16条黄金法则
  • Flask 介绍
  • JAVA基础知识点3 (String 和 StringBuffer 以及 StringBuilder 的特点以及区别)
  • 2024年8月AI内容生成技术的现状与未来:从文生文到跨模态交互的全景分析
  • File 34
  • AI全知道-Embedding model中的Vector知识点
  • Qt 学习第四天:信号和槽机制(核心特征)
  • 跳跃游戏Ⅱ C++简单代码
  • Gitlab中access token 和Deploy token的区别