【数据结构(邓俊辉)学习笔记】图03——拓扑排序

文章目录

  • 0. 概述
  • 1. 零入度算法
    • 1. 1 拓扑排序
    • 1. 2 算法
  • 2. 零出度算法
    • 2.1 算法
    • 2.2 实现
    • 2.3. 复杂度

0. 概述

学习下拓扑排序

1. 零入度算法

1. 1 拓扑排序

在这里插入图片描述
首先理解下拓扑排序

其实老师经常干这事,如编讲义,将已经知道的知识点串起来变成讲课序列。那怎么串起来呢?将知识点列出,将它们之间的相互关系描述下。要讲priority queue那上一讲需要讲什么内容,要讲hashing需要讲哪些内容,需要罗列出来。但是讲课不可能像分支一样平行一分为二裂开,最终都会变成下面这样平坦的线性序列。

在这里插入图片描述

(续)一个好的安排是什么呢?每当讲到一个知识点时,它所依赖的知识点都应该在此前依然讲过,这样就会变成一个线性序列。将原来图中所有的点整理成这样一个线性次序,前面点与后面点的边次序都是前指向后,没有后指向前,这就是对原图的拓扑排序。

1. 2 算法

  • 如果真有这么一个图,怎么排呢?
    在这里插入图片描述
    因为这个图有依赖关系,所以是不折不扣的有向图,但有意思的是这里不能有环,如果有环路就有问题。

在这里插入图片描述
首先需要找到零入度的点——无任何依赖,在dag图中必然有这么一个点,由于DAG子图亦为DAG,于是可以利用减而治之思想,将这个零入度的点抹掉,接着找下一个零入度点。

  • 那么这个算法如何实现?

在这里插入图片描述
图中已经有零入度的点A或B,任取一个,这里取A,放入队列中,等价将A点及其边从图中删除。由于DAG的子图亦是DAG,所以还会有零入度的点,将B点放入队列中,然后依次类推,当所有的点都放入队列后,队列中的节点顺序就是拓扑排序。

但这个方法并不好,实现起来比较麻烦,需要每次去找那个零入度的点,而且删除点及其边的时候还要更新相应信息,可能会对图产生伤害,那怎么做呢?看下下面的零出度算法

2. 零出度算法

2.1 算法

说服下自己,DAG既有零入度点也有零出度点,这个很重要,为什么这么讲,因为之前的DFS(深度优先搜索)可以帮我们实现这个方法。
在这里插入图片描述
这样要做的事就比较简单,不需要零入度算法那这样改改度数等等。之前已经造出DFS算法,这样就可以搭DFS便车实现零出度算法。

如何实现呢?

2.2 实现

在这里插入图片描述
这里引入一个栈,排序结果将以逆序打印出来。随便找一个点,这里首先访问顶点V,将顶点V状态初始值设置为DISCOVERED,接着枚举V的所有邻居,视u的状态,分别处理,后续会做分析。访问所有邻居后,将顶点V的状态设置为VISITED,然后顶点V入栈。

接着还有顶点V的邻居处理方法还未做交代,怎么处理呢?
在这里插入图片描述

  1. 若顶点U的状态为UNDISCOVERED,更新顶点U的父亲为V,边的状态为TREE,作递归调用,从顶点u处深入。
  2. 顶点U的状态为DISCOVERED,一旦发现后向边,即图非DAG图,无拓扑排序,则退出而不再深入。
  3. 顶点U的状态为VISITED,更新下顶点状态。

2.3. 复杂度

这里仅额外引入的栈,规模不超过顶点总数O(n)。总体而言,空间复杂度与基本的深度优先搜索算法同样,仍为O(n + e)。该算法的递归跟踪过程与标准DFS搜索完全一致,且各递归实例自身的执行时间依然保持为O(1),故总体运行时间仍为O(n + e)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/693053.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Vivado时序报告之Datasheet详解

目录 一、前言 二、Datasheet配置选项说明 2.1 Options 2.2 Groups 2.3 Timer Settings 2.4 Common Options 三、Datasheet报告 3.1 General Information 3.2 Input Ports Setup/Hold 3.3 Output Ports Clock-to-out 3.4 Setup between Clocks 3.5 Combinational…

盘点 2024 Google I/O 中的 Android 方向关键更新

这里写自定义目录标题 前言1. AI 编程助手2. 生成式AI 应用3. 不同屏幕尺寸适配4. 桌面小部件(Widget)5. 跨设备类型开发6. WearOS & 可穿戴7. Android for Car8. Android TV9. Google Home API10. Kotlin Multiplatform11. Jetpack Compose12. Andr…

HTML+CSS+JS 密码灯登录表单

效果演示 实现了一个登录页面,包括一个标题、两个输入框(用户名和密码)、一个登录按钮和一个眼睛图标。点击眼睛图标可以显示或隐藏密码。页面背景有两个圆形的半透明元素,整个页面使用了flex布局,并且在水平和垂直方向上都居中对齐。登录框使用了阴影效果和圆角边框,并且…

Jmeter 压力测测试的简单入门

下载安装 官方网站:Apache JMeter - Download Apache JMeter 下载完成解压即可。 配置 1. 找到 bin 目录下的 ApacheJMeter.jar 包,直接打开 如果向图片这样不能直接打开,就在此路径运行 CMD,然后输入下面的命令即可启动。 ja…

微信小程序学习笔记(4)

文章目录 1、< template >< / template >2、样式导入i、wxmlii、wxss 3、flex布局i、容器属性ii、项目属性 1、< template >< / template > 模板可以重复调用 首先要定义一个模板&#xff1a; <template name"test"><view>{{…

Python GUI编程:深入探索现代GUI库及其创新应用

目录 引言 Python GUI库概览 1. Tkinter 2. PyQt/PySide 3. wxPython 4. Kivy 5. PyGTK 6.FLTK (pyFLTK) 创新应用案例 1. 交互式数据分析工具 2. 智能物联网(IoT)仪表板 3. 增强现实(AR)辅助设计软件 4. 跨平台的科学计算软件 5. 交互式教育软件 实战示例1&…

Springboot整合SpringCache+redis简化缓存开发

使用步骤&#xff1a; 1.引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-cache</artifactId> </dependency><dependency><groupId>org.springframework.boot</groupI…

MySQL—多表查询—标量子查询

一、引言 上篇学习完子查询的概念和分类。 现在来学习第一种子查询——标量子查询。 &#xff08;1&#xff09;标量子查询的基本概念 子查询返回的结果是单个值&#xff0c;也就是一行一列&#xff08;可以是数字、字符串、日期等&#xff09; 是一种最简单的子查询形式&am…

【机器人和人工智能——自主巡航赛项】进阶篇

文章目录 案例要求创建地图rviz仿真 保存地图坐标点定位识别训练主逻辑理解语音播报模块匹配二维码识别多点导航讲解视频其余篇章 案例要求 创建地图 ./1-gmapping.sh 把多个launch文件融合在sh文件里面 rviz仿真 rviz是rose集成的可视化界面&#xff0c;查看机器人的各项数…

iOS--block再学习

block再学习 什么是blockblock是带有自动变量的匿名函数block语法 block的实现block的实质截获自动变量__blcok说明符Block存储域__block变量存储域使用__block变量用结构体成员变量__forwarding的原因 截获对象 什么是block Block时c语言的扩充功能&#xff0c;它允许开发者定…

宝塔面板和 LNMP 环境下反代 HFish 蜜罐平台的正确方法

最近明月在热心站长好友的支持下搭建了安全、简单、有效并永久免费的蜜罐平台 HFish,因为 HFish 默认是以 https://IP:端口 的 Web 链接形式提供访问的,这会暴露蜜罐平台的真实服务器 IP 不说,还非常不便于快速的访问(反正明月是记不住 IP 的),所以就需要给部署好的 HFis…

Python爬取与可视化-豆瓣电影数据

引言 在数据科学的学习过程中&#xff0c;数据获取与数据可视化是两项重要的技能。本文将展示如何通过Python爬取豆瓣电影Top250的电影数据&#xff0c;并将这些数据存储到数据库中&#xff0c;随后进行数据分析和可视化展示。这个项目涵盖了从数据抓取、存储到数据可视化的整个…

《精通ChatGPT:从入门到大师的Prompt指南》第4章:避免常见错误

第4章&#xff1a;避免常见错误 在使用ChatGPT进行Prompt编写时&#xff0c;常见的错误可能会大大影响生成内容的质量和准确性。本章将详细讨论这些错误&#xff0c;并提供如何避免它们的建议。 4.1 不明确的指令 在使用ChatGPT时&#xff0c;一个常见的问题是指令不够明确。…

中电联系列二:rocket手把手教你理解中电联协议!

分享《一套免费开源充电桩物联网系统&#xff0c;是可以立马拿去商用的&#xff01;》 前 言 T/CEC102《电动汽车充换电服务信息交换》分为四个部分&#xff1a; ——第1部分&#xff1a;总则&#xff1b; ——第2部分&#xff1a;公共信息交换规范&#xff1b; ——第3部分&a…

微信机器人实现OCR识别录入数据

介绍 采用微信的hook插件&#xff0c;然后解析微信发来的数据图片&#xff0c;通过ocr识别 然后将数据落入execl表格中。同时有权限的人可以导出数据表格即可。 流程图 代码片 文本消息处理流程_robot.py elif msg.type 0x01: # 文本消息# 管理员列表dba_user_list [wxid_…

MathType7.8永久破解版下载 让数学学习变得简单有趣!

大家好&#xff0c;我是科技评论家。今天给大家推荐一款非常实用的数学公式编辑器——MathType 7.8&#xff01;&#x1f4f1;&#x1f4b0; 在数字化时代&#xff0c;学术研究、教学和科研领域中的数学公式编辑需求越来越高。而MathType 7.8作为一个广受欢迎的数学公式编辑器&…

Spring Boot整合Redis通过Zset数据类型+定时任务实现延迟队列

&#x1f604; 19年之后由于某些原因断更了三年&#xff0c;23年重新扬帆起航&#xff0c;推出更多优质博文&#xff0c;希望大家多多支持&#xff5e; &#x1f337; 古之立大事者&#xff0c;不惟有超世之才&#xff0c;亦必有坚忍不拔之志 &#x1f390; 个人CSND主页——Mi…

DALL·E2最详细解读篇章

CLIP被证明其可以学习到鲁棒的图像特征&#xff0c;可以有效的捕获图像的语义和风格&#xff0c;且具有很强的zero-shot能力。另外&#xff0c;Diffusion是目前最优的生成式框架&#xff0c;其推动了图像、视频生成任务的最先进性能。Classifier-Free Diffusion指导技术以样本多…

Junit 单元测试 详解,包你掌握

Java单元测试----Junit详解 1 什么是 Junit JUnit 是一个广泛使用的 Java 单元测试框架。它用于编写和运行可重复的测试&#xff0c;以验证 Java 程序的行为是否符合预期 也许有人会好奇&#xff0c;之前学的 Selenium 和 Junit 有什么关系&#xff1f;答案就是没关系&#…

递归【2】(组合回溯(生成括号)、子集回溯(背包问题))

括号对 &#xff08;组合型回溯&#xff09; 分解成子问题&#xff0c;每一次添加括号分两步&#xff1a; if左括号小于n&#xff0c;加左括号&#xff0c;然后k(index1), if左括号大于有括号&#xff0c;加右括号&#xff0c;k(index1),然后收尾括号单独考虑&#xff0c;到…