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

图论拓扑排序

拓扑排序(有向无环图):事件之间存在依赖关系,事件A依赖于事件B,那么A的实现的前提是B先实现

对于图论来说,图谱排序就是将一个有向图转换成线性的排序,其中很重要的一点是判断图中有无环,即存在循环依赖的话就不能做线性排序。

BFS和DFS都可以,掌握BFS(卡恩算法)

步骤:

  1. 优先找到入度为0的节点,它是起点,加入结果集
  2. 将该节点从图中移除

拓扑排序就是重复以上过程,如果找不到入度为0的节点说明有环,拓扑算法也是判断有向环的方法。

       第一次写,忘记在广搜的过程中判断当前文件是否有后续文件了

可以用邻接表存有向图,别忘记初始化表的大小,使用邻接表的好处
          遍历更高效:没有引入哈希结构,更适合图

        更小的内存开销:map需要维持平衡树的结构,unordered_map也要维持哈希桶,相比下vector开销更小

        避免隐式初始化:如果u不存在,map会自动创建一个u,可能引起bug

http://www.xdnf.cn/news/5542.html

相关文章:

  • 前端 CSS 样式书写与选择器 基础知识
  • 反转链表 - 简单
  • SET NX互斥功能的实现原理
  • 【AI大语言模型本质分析框架】
  • 在Mac环境下搭建Docker环境的全攻略
  • 技术视界 | 青龙机器人训练地形详解(四):复杂地形精讲之斜坡
  • 因子分析基础指南:原理、步骤与地球化学数据分析应用解析
  • 数据出境的安全合规思考
  • 17.three官方示例+编辑器+AI快速学习webgl_buffergeometry_lines
  • LabVIEW中算法开发的系统化解决方案与优化
  • 如何查看电脑处理器配置 电脑处理器查看方法
  • CSP-J普及组第一轮真题单选题专项训练(一)
  • 欧姆龙CJ/CP系列PLC串口转网口模块:工业通信的智能桥梁
  • 矩阵置零算法讲解
  • 跨时钟域(CDC,clock domain crossing)信号处理
  • 新型.NET恶意软件“PupkinStealer“窃取浏览器凭证并通过Telegram外传
  • window 显示驱动开发-指定 DMA 缓冲区的段
  • .NET 8 + Angular WebSocket 高并发性能优化
  • Matlab 模糊控制平行侧边自动泊车
  • MySQL之GET_JSON_OBJECT函数
  • Express知识框架
  • Linux常用命令详解(下):打包压缩、文本编辑与查找命令
  • C++GO语言微服务之Dockerfile docker-compose
  • 手机换地方ip地址会变化吗?深入解析
  • CSS3 伪元素(Pseudo-elements)大全
  • 【HarmonyOS Next之旅】DevEco Studio使用指南(二十二)
  • 【25软考网工】第六章(4)VPN虚拟专用网 L2TP、PPTP、PPP认证方式;IPSec、GRE
  • USB传输模式
  • 大语言模型强化学习双强:OpenRLHF与verl技术解析
  • Golang空接口的用途详解