拓扑排序

来自计算思维百科
跳转至: 导航搜索
拓扑排序1.png

我们在完成一个较大的工程时,往往需要把这个工程划分成许多子工程。在整个工程中,有些子工程必须在其它有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子工程的结束为先决条件的,但有些子工程没有先决条件,可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程之间的先后关系,可用一个有向图来表示,图中的顶点代表活动,图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行。确定这些点间顺序的过程就是拓扑排序。

基本概念

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

应用范围

拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。例如,在日常工作中,可能会将项目拆分成A、B、C、D四个子部分来完成,但A依赖于B和D,C依赖于D。为了计算这个项目进行的顺序,可对这个关系集进行拓扑排序,得出一个线性的序列,则排在前面的任务就是需要先完成的任务。

使用方法及步骤

拓扑排序算法主要是循环执行以下两步,直到不存在没有前趋的顶点为止。

(1) 选择不需要前趋的顶点(就是没有条件的顶点)并输出之;

(2) 从网中删除此顶点及所有出边。

循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。

应用案例

应用1- 课程学习安排

案例:一个软件专业的学生必须学习一系列基本课程,其中有些课程是基础课,它独立于其他课程,如《高等数学》;而另一些课程必须在学完作为它的基础课程(前导课程)才能开始。如,在《C++程序设计》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先关系)。这个关系可以用有向图更清楚地表示,如图,图中顶点表示课程,有向边(弧)表示先决条件。若课程i 是课程j 的先决条件,则图中有弧<I,j>。

课程编号

课程名称

先决条件

C1

高等数学

C2

C++程序设计

C3

离散数学

C1,C2

C4

数据结构

C2,C3

我们可以画出表示课程之间优先关系的有向图:

拓扑排序2.png

由上面的有向图有如下一个拓扑有序序列:

(C1,C2,C3,C4)

若某个学生每学期只学一门课程的话,他必须按照拓扑有序序列来安排学习计划。

可以体现的计算思维

拓扑排序通过各步骤之间的前后约束关系,确定一个步骤序列,是一种将实际问题抽象为图并进行求解的过程,体现了计算思维的抽象特点。