什么是拓扑排序?简单的说,就是由某个集合上的一个偏序序列得到该集合上的一个全序序列,这个操作称之为拓扑排序。
那么,我们首先来回顾一下离散数学中的关于偏序和全序的定义:
若集合X上的关系R是自反的,反对称的和传递的,则称R是集合X上的偏序关系。
设R是集合X上的pain徐,如果对每个x,y输入X,必有xRy或者yRx,则称R是集合X上的全序关系。
举个简单的例子说明什么是拓扑排序。
现在到大学了,作为计算机系的学生,要学习很多与计算机相关的课程:有c语言,c++,java,数据结构,离散数学,线性代数,高等数学,编译原理,操作系统,组成原理,软件工程等等。。。
但是,如果你要学习数据结构,你就必须有离散数学和C语言的功底,那么在安排教学顺序时,就必须保证C语言和离散数学要学完再开数据结构。
还有一类,比如高等数学,它与数据结构没有关系,但是和线性代数有关系,这时,我们需要独立考虑高等数学,而不需要考虑C语言和离散数学。
以此类推,我们可以得到一张图。途中的关系就代表了教学的顺序。
那么,如何进行拓扑排序呢?很简单
1.在有向图中选一个没有前驱的项目且输出之。
2.从途中删除该顶点和所有以它为尾的弧。
3.重复上述两个步骤,直到全部顶点均已输出,或者当前图中不存在无前驱的顶点位置。后一种情况则说明有向图中存在环。在AOV-网中,不应该出现有向环,因为存在环就意味着某项活动以自己发生作为发生的条件,显然是很荒谬的。
之后,我们便完成了拓扑排序,拓扑排序可能有多个排序序列,我们只需要挑出满足题意的那种就可以了。。。
分享到:
相关推荐
课题二 拓扑排序 2.1 问题的提出2.1 问题的提出 任务:编写函数实现图的拓扑排序。 程序所实现的功能: 建立对应的邻接表,对该图进行拓扑排序,并显示排序结果。 输入: 顶点数, 边数及各顶点信息(数据格式为整形...
任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出...
拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序
对于有向图进行拓扑排序,图使用邻接矩阵的存储结构。
C语言实现图的拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...
拓扑排序源码,程序简单易懂,注释详细。希望对学习数据结构的朋友有所帮助。
拓扑排序关键路径算法C语言完整代码,vs2013下编译运行通过
题目内容:输出有向网的拓扑排序序列。 拓扑排序的基本思想为: 1)从有向图中选出一个无前驱的顶点输出; 2)将此顶点和以他为起点的弧删除; 3)重复1)2)直到不存在无前驱的顶点; 4)若此时输出的顶点数小于有...
拓扑排序与关键路径,在日常生活中,一项大的工程可以看作是由若干个子工程(这些子工程称为“活动” )组成的集合,这些子工程(活动)之间必定存在一些先后关系,即某些子工程(活动)必须在其它一些子工程(活动...
数据结构课设报告,包括完整源代码,用拓扑排序算法安排有先后制约关系的课程的教学计划。
C实现的拓扑排序,有详细注释,有问题的我们一起讨论
图的最短路径、拓扑排序和关键路径相关算法描述,有c++code
拓扑排序 数据结构 c和 C++源程序代码 拓扑排序 数据结构 c和 C++源程序代码
基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助
阅读了《数据结构(C语言)》的经典著作后...本次算法课程设计运用所学的图论的拓扑排序和关键路径,去实现工程中的花费时间和顺利进行问题。拓扑排序主要用于检验工程能否施工,关键路径主要用于看出工程施工时间消耗。
C# 图 拓扑排序
【拓扑排序】 任务:编写函数实现图的拓扑排序。 ........................................................................................................................
图 拓扑排序 深度搜索 广度搜索 最小生成树
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...