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

2024-06-09 12:52

本文主要是介绍【数据结构(邓俊辉)学习笔记】图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)。

这篇关于【数据结构(邓俊辉)学习笔记】图03——拓扑排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert