精华内容
下载资源
问答
  • 拓扑排序空间复杂度
    万次阅读 多人点赞
    2017-04-12 10:34:35

    AOV网络

      在有向图中,用顶点表示活动,用有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行。这种有向图叫作顶底表示活动的网络(Active on vertices),记作AOV网络。 
      在AOV网络中,如果活动Vi必须在Vj之前进行,则存在有向边<Vi, Vj>,并称Vi是Vj的直接前驱,Vj是Vi的直接后继。这种前驱与后继的关系具有传递性和反自反性,这要求AOV网络中不能出现回路,即有向环。因此,对于给定的AOV网络,必须先判断它是否存在有向环。

    拓扑排序

      检测有向环可以通过对AOV网络构造它的拓扑有序序列(即进行拓扑排序,topological sorting)。该过程将各个顶点排列成一个线性有序的序列,使得AOV网络中所有的前驱和后继关系都能得到满足。 
      如果拓扑排序能够将AOV网络的所有顶点都排入一个拓扑有序的序列中,则说明该AOV网络中没有有向环,否则AOV网络中必然存在有向环。AOV网络的顶点的拓扑有序序列不唯一。

    拓扑排序算法的伪代码

    1. 栈S初始化;累加器count初始化;
    2. 扫描顶点表,将没有前驱(即入度为0)的顶点压栈;
    3. 当栈S非空时循环 
      3.1 vj=退出栈顶元素;输出vj;累加器加1; 
      3.2 将顶点vj的各个邻接点的入度减1; 
      3.3 将新的入度为0的顶点入栈;
    4. if (count<vertexNum) 输出有回路信息;

    利用顶点的入度数组建立栈S

      为了建立栈S,可以不另外分配存储空间,直接利用入度数组inDegree[]中为零的元素,同时设立一个栈顶指针top,指示当前栈顶的位置,即某一个入度为零的顶点位置。栈初始化时置top=-1,表示空栈。

    1. 将顶点w进栈时(此时w的入度为0, 不再需要inDegree[w]): 
      count[w] = top; top = w;
    2. 退栈时: 
      v = top; top = inDegree[top]

    算法复杂度

      如果AOV网络有n个顶点,e条边,在拓扑排序的过程中,搜索入度为零的顶点所需的时间是O(n)。在正常情况下,每个顶点进一次栈,出一次栈,所需时间O(n)。每个顶点入度减1的运算共执行了e次。所以总的时间复杂为O(n+e)。

    更多相关内容
  • 什么是拓扑排序

    2021-05-30 21:02:28
    什么是拓扑排序 拓扑排序(Topological Order),很多人听说过,但是不了解的一种算法。或许很多人只知道它是图论的一种排序,至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。 而实质上它只是将DAG...
    1. 什么是拓扑排序
      拓扑排序(Topological Order),很多人听说过,但是不了解的一种算法。或许很多人只知道它是图论的一种排序,至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。

    而实质上它只是将DAG图的顶点排成一个线性序列,得到一个顶点的全序集合。其排序的顺序依据就是节点的指向关系。比如前言的DAG图:
    在这里插入图片描述


    节点5在节点4和节点3的后面
    节点9在节点6和节点7的后面

    那么最后得到的节点的线性序列结果,也一定要满足上面的指向顺序。

    每一个节点都拥有入度(有多少点导向它,也就是开始它有多少前提)和出度(它导向多少点,也就是它是多少其他节点开始的前提)。例如节点5的入度为3和4,出度为7。

    拓扑排序的结果不是唯一的,只要符合上面的条件,那么它就是拓扑序列,比如1 2 4 3 6 5 7 9和2 1 3 4 5 6 7 9,这两个结果都是可行的。

    官方一点的定义:将有向图中的节点以线性方式进行排序。即对于任何连接自节点u到节点v的有向边uv,在最后的排序结果中,节点u总是在节点v的前面。
    2. 现实案例
    看了上面关于拓扑排序的概念如果还觉得十分抽象的话,那么不妨考虑一个非常非常经典的例子——选课。

    假设我非常想学习一门《jsp入门》的课程,但是在修这么课程之前,我们必须要学习一些基础课程,比如《JAVA语言程序设计》,《HTML指南》等等。那么这个制定选修课程顺序的过程,实际上就是一个拓扑排序的过程,每门课程相当于有向图中的一个顶点,而连接顶点之间的有向边就是课程学习的先后关系。

    只不过这个过程不是那么复杂,从而很自然的在我们的大脑中完成了。将这个过程以算法的形式描述出来的结果,就是拓扑排序。

    image

    可以看到,上图中的学习顺序,就是拓扑序列,其不止一个结果。

    拓扑排序算法在工程学中十分重要。

    节点成环的图,无法被拓扑排序,因为这在工程上本身没有意义,比如A——>B——>C——>A,那么这个工程永远无法被开始。
    3. 算法实现
    拓扑排序的最优时间复杂度是O(m+n),其中m和n是DAG图中节点数和边数。因为拓扑排序至少要对DAG图的节点和边进行一次完整的遍历。

    拓扑排序的最优空间复杂度是O(m+n),其中m和n是DAG图中节点数和边数。我们一般使用邻接表来存储DAG图,因此空间复杂度是O(m+n)。

    展开全文
  • 前言在正文开始前,我们先来了解一下有向无环图(Directed Acyclic Graph简称DAG)如下图就是一个DAG图,DAG图是我们讨论拓扑排序的基础。AOV网:数据在顶点 可以理解为面向对象AOE网:数据在边上,可以理解为面向过程...

    前言

    在正文开始前,我们先来了解一下有向无环图(Directed Acyclic Graph简称DAG)

    如下图就是一个DAG图,DAG图是我们讨论拓扑排序的基础。

    AOV网:数据在顶点 可以理解为面向对象

    AOE网:数据在边上,可以理解为面向过程!

    1. 什么是拓扑排序

    拓扑排序(Topological Order),很多人听说过,但是不了解的一种算法。或许很多人只知道它是图论的一种排序,至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。

    而实质上它只是将DAG图的顶点排成一个线性序列,得到一个顶点的全序集合。其排序的顺序依据就是节点的指向关系。比如前言的DAG图:

    ...

    节点5在节点4和节点3的后面

    节点9在节点6和节点7的后面

    ...

    那么最后得到的节点的线性序列结果,也一定要满足上面的指向顺序。

    每一个节点都拥有入度(有多少点导向它,也就是开始它有多少前提)和出度(它导向多少点,也就是它是多少其他节点开始的前提)。例如节点5的入度为3和4,出度为7。

    拓扑排序的结果不是唯一的,只要符合上面的条件,那么它就是拓扑序列,比如1 2 4 3 6 5 7 9和2 1 3 4 5 6 7 9,这两个结果都是可行的。

    官方一点的定义:将有向图中的节点以线性方式进行排序。即对于任何连接自节点u到节点v的有向边uv,在最后的排序结果中,节点u总是在节点v的前面。

    2. 现实案例

    看了上面关于拓扑排序的概念如果还觉得十分抽象的话,那么不妨考虑一个非常非常经典的例子——选课。

    假设我非常想学习一门《jsp入门》的课程,但是在修这么课程之前,我们必须要学习一些基础课程,比如《JAVA语言程序设计》,《HTML指南》等等。那么这个制定选修课程顺序的过程,实际上就是一个拓扑排序的过程,每门课程相当于有向图中的一个顶点,而连接顶点之间的有向边就是课程学习的先后关系。

    只不过这个过程不是那么复杂,从而很自然的在我们的大脑中完成了。将这个过程以算法的形式描述出来的结果,就是拓扑排序。

    可以看到,上图中的学习顺序,就是拓扑序列,其不止一个结果。

    拓扑排序算法在工程学中十分重要。

    节点成环的图,无法被拓扑排序,因为这在工程上本身没有意义,比如A——>B——>C——>A,那么这个工程永远无法被开始。

    3. 算法实现

    拓扑排序的最优时间复杂度是O(m+n),其中m和n是DAG图中节点数和边数。因为拓扑排序至少要对DAG图的节点和边进行一次完整的遍历。

    拓扑排序的最优空间复杂度是O(m+n),其中m和n是DAG图中节点数和边数。我们一般使用邻接表来存储DAG图,因此空间复杂度是O(m+n)。

    3.1 广度优先搜索法(BFS)

    3.1.1 BFS实现拓扑排序

    广度优先搜索法的思路很简单:

    从DAG图中找到入度为0的节点A(也就是没有箭头指向它的节点),将其放入拓扑序列的结果集。

    同时删除由节点A出发的所有边。

    在剩下的DAG图中重复1-2两步。

    如果最后可以把全部的节点都删除并加入到结果集,那表示DAG图可以被拓扑排序;否则,如果最后有节点被剩下,那说明该图是有环图,无法被拓扑排序。

    如下图

    3.1.2 BFS实现拓扑排序的优化

    如果有时候,我们只需要知道某个DAG图是否可以拓扑排序,而不需要真正得到拓扑排序后的结果,那么可以不需要结果集列表,只需要统计被删除的节点的数量即可,如果该数量等于DAG图的节点数,那么DAG图可以被拓扑排序。

    3.2 深度优先搜索法(DFS)

    3.2.1 DFS实现拓扑排序

    深度优先搜索法是广度优先搜索法的逆向思路,它的步骤如下:

    选取图中任意一个节点A,将其状态标记为“搜索中”

    寻找节点A的邻接点(沿着箭头指向寻找相邻的节点)

    如果A存在邻接点

    如果A的邻接点中存在状态为“搜索中”的邻接点,那么表示DAG图有环路,不可拓扑排序。

    否则,那么任意选择一个状态为“未搜索”的邻接点B,使用递归对B重复做1和2操作,注意此时B的邻接点判断不包含来路(也就是A节点)。等到A的所有邻接点都被搜索到,递归回溯回A节点的时候,那么A节点也会被标记为“已搜索”,并压入结果栈。

    如果A不存在邻接点,那么将节点A的状态改为“已完成”,并且将其压入一个结果集的栈中。

    A节点及其相邻节点都搜索完毕后,如果还有未搜索的节点,那么任意选取一个节点当做出发点,继续重复1,2,3步骤。

    直到所有的节点都被搜索并压入栈,那么此时结果栈中,从栈顶到栈底的顺序,就是拓扑排序的顺序。

    3.2.2 DFS实现拓扑排序的优化

    如果有时候,我们只需要知道某个DAG图是否可以拓扑排序,而不需要真正得到拓扑排序后的结果,那么可以不需要结果栈,只需要判断整个深度优先搜索过程,没有发生“搜索中”节点的相邻节点(不包含来路的节点)也是“搜索中”就行。

    4 算法题解

    4.1 课程表I

    4.2 课程表II

    展开全文
  • 拓扑排序 一个无环的有向图称作有向无环图。简称DAG图。 有向无环图是描述含有公共子式的表达式的有效工具。可以利用有向无环图,则可以实现对相同子式的共享,从而节省存储空间。 AOV网(顶点表示活动的网):在一...

    拓扑排序

    一个无环的有向图称作有向无环图。简称DAG图。
    在这里插入图片描述
    有向无环图是描述含有公共子式的表达式的有效工具。可以利用有向无环图,则可以实现对相同子式的共享,从而节省存储空间

    AOV网(顶点表示活动的网):在一个(用DAG图)表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系。

    拓扑序列:由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
    拓扑排序是一个有向无环图(DAG)的所有顶点的线性序列。且该序列必须满足下面两个条件:

    1. 每个顶点出现且只出现一次。

    2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

    拓扑排序是对一个有向图构造拓扑序列的过程。

    DAG图拓扑排序的算法思想

    1. 在有向图中选择一个没有前驱的顶点且输出之。
    2. 在图中删除该顶点和它射出的所有弧
    3. 重复上述两步,直到全部顶点均已全部输出,或者当前图中不存在没有前驱的顶点为止。
      ◆ 后一种情况说明有向图中肯定存在环

    DAG图拓扑排序的算法步骤

    1. 将邻接表中所有入度为0的顶点进栈
    2. 栈非空时,弹出栈顶元素Vj
      在邻接表中查找Vj的直接后继Vk,将Vk的入度减1
      若Vk的入度为0则进栈
    3. 重复上述操作直至栈空为止
      若栈空时输出的顶点个数不是n,则有向图有环

    拓扑排序:如果图中有一条从u到v的路径,则顶点v必须出现在顶点u之后。找出顶点活动网中的拓扑序列称“拓扑排序”。

    拓扑排序的过程
    在这里插入图片描述

    在这里插入图片描述
    邻接表:
    在这里插入图片描述
    由以上步骤得拓扑有序序列为0,1,3,2,5,4,6

    拓扑排序既可用深度优先搜索,也可用广度优先搜索实现。

    时间复杂度为O(n+e)

    关键路径

    AOE网(活动在边上): AOE网是一个带权的有向无环图。其中顶点表示事件,弧表示活动,权表示活动持续的时间

    AOE网与AOV网的相同点:

    • 都是有向无环图。

    AOE网与AOV网的不同点:

    • AOE网的边表示活动,边有权值,边代表活动持续时间顶点表示事件,事件是图中新活动开始或者旧活动结束的标志。
    • AOV网的顶点表示活动,边无权值,边代表活动之间的先后关系

    在这里插入图片描述
    AOE图的性质:

    • 所有AOE-网只有一个源点入度为0的点)和一个汇点出度为0的点)。
      例如:V1表示整个工程开始,V9表示整个工程结束。
    • 只有进入某顶点的各个活动结束,该顶点所代表的事件才能发生;
      只有某顶点所代表的事件发生, 从该顶点出发的各个活动才能开始(例如:顶点V5)。

    关键路径
    定义:在AOE网中,从源点从汇点的所有路径中,具有最大路径长度的路径称为关键路径。

    假设开始点是V1,从V1到Vi的最长路径长度叫做事件Vi的最早发生事件。(这个事件决定了所有以Vi为尾的弧所表示的活动的最早开始时间。)

    • e(i)表示活动ai的最早开始的时间
    • l(i)表示活动ai的最迟的开始时间;
    • 两者之差l(i)-e(i)意味着完成活动ai的时间余量。
    • 关键活动:l(i)=e(i)
      在这里插入图片描述

    概念:
    假设:活动ai由弧<j , k>表示,持续时间为dut(<j , k>)

    • 事件Vj的最早发生时间ve(j) :源点到Vj 最长路径的长度
      ◆ 典例:事件V5的最早发生时间(正(源点往后)推为7

    在这里插入图片描述
    假设:活动ai由弧<j , k>表示,持续时间为dut(<j , k>)

    • 活动ai的最早开始时间e(i): 由性质2,e(i)决定了
      所有以Vj为尾的弧,所表示活动的最早开始时间
      典例 :活动a7和a8的最早开始时间(7,由定义可知)
      性质3: e(i)=ve(j)
      ◆ e(i)=ve(j)的意义:活动最早开始时间由射出结点决定
      在这里插入图片描述

    假设:活动ai由弧<j , k>表示,持续时间为dut(<j , k>)

    • 事件Vk的最迟发生时间vl(k) :Vk到汇点最长路径的长度
      典例:事件V8的最迟发生时间(倒推为14
      在这里插入图片描述
      假设:活动ai由弧<j , k>表示,持续时间为dut(<j , k>)
    • 活动ai的最迟开始时间l(i):由vl(k)倒推
      ◆ 典例:活动a9的最迟开始时间(倒推为10)
      ◆ 性质4: l(i)=vl(k)- dut(<j , k>)
      ◆ 利用性质 l(i)=vl(k)- dut(<j , k>在这里插入图片描述
    • 定义:完成活动ai的时间余量: l(i)-e(i)
      ◆ 定义:l(i)=e(i)的活动称为关键路径/非关键路径的含义

    在这里插入图片描述

    • 归纳:重要性质

    ⑴ 性质3: e(i)=ve(j)
    ⑵ 性质4: l(i)=vl(k)- dut(<j , k>)
    意义:将e和l的求解转换为ve和vl的求解
    ⑶ 关键路径算法
    在这里插入图片描述
    关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。

    展开全文
  • 拓扑排序

    2021-05-21 20:56:11
    拓扑排序:在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序: ① 每个顶点出现且只出现一次。 ② 若顶点A在序列中排在顶点B的前面,则在图中不存在从顶点B到顶点A的...
  • 拓扑排序的两种实现
  • 下面的算法都打包在一个应用当中,你只需要下载安装即可,里面有算法的介绍,时间复杂度,空间复杂度,代码示例 二叉树的遍历 二叉排序树 红黑树 AVL树 图的邻接表存储构成图 有向图的创建 拓扑排序-邻接矩阵存储-...
  • 拓扑排序(topological sorting)介绍及Python实现,介绍了拓扑排序基本算法原理,并给出基于深度优先搜索和基于广度优先搜索的Python实现。
  • //拓扑排序成功 } 运行结果 程序分析 由于输出每个顶点的同时还要删除以它为起点的边,故采用邻接表法来拓扑排序的时间复杂度为O(|V|+|E|); 算法实现(深度优先遍历—DFS算法) 对于有向无环图G中的任意结点u、v,...
  • 我们知道利用邻接矩阵进行拓扑排序时,程序实现较为简单,但是效率不高,算法的复杂度为O(n^3).而利用邻接表会使入度为0的顶点的操作简化,从而提高算法的效率。 在邻接表存储结构中,为了便于检查每个顶点的入度,...
  • 什么是拓扑排序拓扑排序,对一个有向无环图(DirectedAcyclicGraph简称DAG)(Directed Acyclic Graph简称DAG)(DirectedAcyclicGraph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对...
  • 带你了解有向无环图和拓扑排序

    千次阅读 2020-04-09 19:19:42
    而提到DAG,就差不多会联想到拓扑排序拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序的操作。拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。拓扑排序是对有向无环图的顶点的一种排序,它使得...
  • 用字符文件提供数据建立DAG(有向无环图)合适的存储结构。编写程序,输出所有可能的拓扑排序序列。...课程设计报告要求给出详细算法描述,在结论部分应分析算法的时间复杂度和空间复杂度,并给出分析的结果。
  • 简而言之,如果G中有环,那就不存在拓扑排序,同时,拓扑排序也不止一种形式。 使用DFS 思路:对于一个节点,如果它的相邻节点都被访问完成,则回溯到它的时候,它也被访问完成,并将其放入ans。由递归的特性可以...
  • 基本概念: 一个无环的有向图称为有向无环图(Directed Acycline Graph,DAG)。 有向无环图是描述一个工程、计划、生产、...拓扑排序是指将 AOV 网中的顶点排成一个线性序列,该序列必须满足:若从顶点 i 到顶点..
  • 建立0入度顶点栈的时间复杂度为O(n),在拓扑排序中若有向图无环,则每个顶点进一次栈出一次栈,所以总的时间复杂度为O(n+e) 来源:oschina 链接:https://my.oschina.net/u/4386188/blog/4503316
  • 空间复杂度 O(N + M): 为建立邻接表所需额外空间,adjacency 长度为 N ,并存储 M 条临边的数据。 二、Leetcode210题:课程表 || 1.题目描述 现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。...
  • 如果答案中包含了这 n个节点,那么我们就找到了一种拓扑排序,否则说明图中存在环,也就不存在拓扑排序了。 深度优先搜索 class Solution { public: vector> redges; vector visited; bool valid = true; void dfs...
  • 如果答案中包含了这 n个节点,那么我们就找到了一种拓扑排序,否则说明图中存在环,也就不存在拓扑排序了。 深度优先搜索 class Solution { public: vector> redges; vector visited; vector ans; bool valid = true...
  • 拓扑排序来输出图的依赖关系

    千次阅读 2019-10-22 15:40:55
    拓扑排序,解决局部依赖输出顺序问题。
  • 拓扑排序详解

    2020-09-09 10:17:34
    拓扑排序详解 本文转载自https://blog.csdn.net/qq_35644234/article/details/60578189 前言 The time of test,family is best. Name:Willam Time:2017/3/6 1、拓扑排序的介绍 对一个有向无环图(Directed Acyclic ...
  • 拓扑排序是指在有向图中的顶点序列,且序列满足若存在从a到b的路径,那么b排在a之后的性质。拓扑常用来检测图中是否存在环。how?入度:设有向图中有一结点v,其入度即为当前所有从其他结点出发,终点为v的的边的数目...
  • 数据结构——图——拓扑排序算法 对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者AOV 网中不存在入度为0的...
  • 本文为拓扑排序的一道经典例题,也可以用深度优先搜索进行完成,重点是对场景的分析以及对中间用到的数据以什么样的形式进行记录和保存,最后是中间过程代码的优化。
  • 拓扑排序 首先要说明一下,拓扑排序不是一种排序方式,而是做一系列事件的可行次序。我们日常生活中,有时必须先完成一些事情,然后才能做另外一些事情。举个例子,我们学数学的时候,一定是先学习加减法,然后学乘...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,832
精华内容 3,932
关键字:

拓扑排序空间复杂度

友情链接: massage.rar