拓扑排序 订阅
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。 [1] 展开全文
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。 [1]
信息
别    称
toposort topsort
应用学科
计算机科学 图论
中文名
拓扑排序
外文名
topological-sort
拓扑排序预备知识
一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子工程的结束为先决条件的,但有些子工程没有先决条件,可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行。通常,我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。 例如,假定一个计算机专业的学生必须完成图3-4所列出的全部课程。在这里,课程代表活动,学习一门课程就表示进行一项活动,学习每门课程的先决条件是学完它的全部先修课程。如学习《数据结构》课程就必须安排在学完它的两门先修课程《离散数学》和《算法语言》之后。学习《高等数学》课程则可以随时安排,因为它是基础课程,没有先修课。若用AOV网来表示这种课程安排的先后关系,则如图3-5所示。图中的每个顶点代表一门课程,每条有向边代表起点对应的课程是终点对应课程的先修课。从图中可以清楚地看出各课程之间的先修和后续的关系。如课程C5的先修课为C2,后续课程为C4和C6。 [2]  一个AOV网应该是一个有向无环图,即不应该带有回路,因为若带有回路,则回路上的所有活动都无法进行。如图3-6是一个具有三个顶点的回路,由边可得B活动必须在A活动之后,由边可得C活动必须在B活动之后,所以推出C活动必然在A活动之后,但由边可得C活动必须在A活动之前,从而出现矛盾,使每一项活动都无法进行。这种情况若在程序中出现,则称为死锁或死循环,是必须避免的。在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列(Topological order),由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的,满足上述定义的任一线性序列都称作它的拓扑序列。由AOV网构造出拓扑序列的实际意义是:如果按照拓扑序列中的顶点次序,在开始每一项活动时,能够保证它的所有前驱活动都已完成,从而使整个工程顺序进行,不会出现冲突的情况。 [2] 
收起全文
精华内容
下载资源
问答
  • 拓扑排序

    2020-12-22 12:22:13
    若图为有向无环图,则可进行拓扑排序拓扑排序的结果为DFS后序遍历的倒序。选课是拓扑排序的经典应用场景之一,即:选修一门课程之前须先修完该课程的前置课程。 class Graph(object): def __init__(self, points_...
  • 主要为大家详细介绍了C++实现拓扑排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 使用简单易懂的回溯算法将拓扑排序的所有序列输出,通过递归和深度优先搜索,核心思想是在查询到结果之后返回到上一级,同时将已访问点的入度加1,使其恢复未访问状态
  • 拓扑排序算法思想

    2018-12-10 15:07:53
    拓扑排序的算法思想和迪杰斯特拉算法思想,浅显易懂,附代码
  • JavaScript的拓扑排序算法。 参见 。 :warning: 该代码要求定义regeneratorRuntime ,例如,通过导入 。 // Sort anything that can be iterated over with `for (const [u, v] of ...)` import { sorted } from...
  • 假设给我们一个任意的图,它可能是也可能不是DAG(有向无圈图),推广拓扑排序算法,以使得给定有向图G的输入,它的输出是以下两者之一: (a) 一个拓扑排序,于是确定了G为DAG; 或者 (b) G中的一个圈,于是确定了G...
  • 拓扑排序(C语言实现)

    2019-03-24 02:05:45
    NULL 博文链接:https://touch-2011.iteye.com/blog/1075871
  • PAGE 数据结构课程设计 设计说明书 有向图拓扑排序算法的实现 学生姓名 樊佳佳 学号 1318064017 班级 网络工程1301 成绩 指导教师 申静 数学与计算机科学学院 2016年1月4日 课程设计任务书 20152016学年第一学期 ...
  • 对于表示有向图的二进制邻接矩阵M,ALLTOPOSORT(M)返回具有所有可能的拓扑排序安排的矩阵。 该函数是 YL Varol 和 D. Rotem 的“生成所有拓扑排序安排的算法”中的算法的实现。
  • 算法设计-拓扑排序

    2017-04-20 20:24:01
    假设给我们一个任意的图,它可能是也可能不是DAG(有向无圈图),推广拓扑排序算法,以使得给定有向图G的输入,它的输出是以下两者之一: (a) 一个拓扑排序,于是确定了G为DAG; 或者 (b) G中的一个圈,于是确定了G...
  • C语言实现图的拓扑排序
  • ACM拓扑排序

    2016-11-25 12:29:53
    假设给我们一个任意的图,它可能是也可能不是DAG(有向无圈图),推广拓扑排序算法,以使得给定有向图G的输入,它的输出是以下两者之一: (a) 一个拓扑排序,于是确定了G为DAG; 或者 (b) G中的一个圈,于是确定了G...
  • 拓扑排序与关键路径,在日常生活中,一项大的工程可以看作是由若干个子工程(这些子工程称为“活动” )组成的集合,这些子工程(活动)之间必定存在一些先后关系,即某些子工程(活动)必须在其它一些子工程(活动...
  • Python实现拓扑排序

    2020-06-07 09:48:33
    用Python借助深度搜索实现节点的拓扑排序,节点有3种颜色表示3种状态。本资源仅作交流学习使用,请勿上传至任何平台和作为作业交给任何学校或机构。
  • 主要介绍了图的应用(最小生成树、拓扑排序、关键路径、最短路径),需要的朋友可以参考下
  • 题目内容:输出有向网的拓扑排序序列。 拓扑排序的基本思想为: 1)从有向图中选出一个无前驱的顶点输出; 2)将此顶点和以他为起点的弧删除; 3)重复1)2)直到不存在无前驱的顶点; 4)若此时输出的顶点数小于有...
  • 因为是有向无环图,所以我们可以在拓扑排序的时候进行dp,循环n个点,复杂度On^2,然后多开一个pre[i][j]记录经过i点时的前一个点。 由于开了两个5000*5000的数组,所以得用int,如果用long long会MLE。 代码如下: ...
  • 拓扑排序C++代码

    2014-10-06 15:23:27
    拓扑排序算法,用C++写的,有注释,适合初学者。
  • 用邻接矩阵实现的拓扑排序,如果不是DAG,会找出有向图中的一个环(NKU算法作业)
  • 主要介绍了Golang实现拓扑排序(DFS算法版),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 拓扑排序关键路径算法C语言完整代码,vs2013下编译运行通过
  • NULL 博文链接:https://128kj.iteye.com/blog/1675685
  • 在AOV网中为了更好地完成工程,必须满足活动之间先后关系,需要将各活动排一个先后次序即为拓扑排序拓扑排序算法void TopologicalSort(ALGraph G) 中,先输出入度为零的顶点,而后输出新的入度为零的顶点,此操作...
  • 有向图的拓扑排序

    2014-08-03 01:17:10
    对于有向图进行拓扑排序,图使用邻接矩阵的存储结构。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,835
精华内容 24,734
关键字:

拓扑排序