拓扑排序8.68.6.1什么是拓扑排序有向图设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1、V2、、Vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若<Vi，Vi>是图中的有向边或者从顶点v到顶点v，有一条路径，则在序列中顶点V必须排在顶点V,之前。在一个有向图G中找一个拓扑序列的过程称为拓扑排序。1/29
设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1、v2、.、vn 称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若<vi，vj>是 图中的有向边或者从顶点vi到顶点vj有一条路径，则在序列中顶点vi必 须排在顶点vj之前。 在一个有向图G中找一个拓扑序列的过程称为拓扑排序。 有向图 1/29
例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业，假设这些课程的名称与相应代号有如下关系：课程代号课程名称先修课程无高等数学C1无C2程序设计C1离散数学C3C4数据结构C2, C3编译原理CsC2, C4Ce操作系统C4, C7C,计算机组成原理C22/29
课程代号 课程名称 先修课程 C1 高等数学 无 C2 程序设计 无 C3 离散数学 C1 C4 数据结构 C2，C3 C5 编译原理 C2，C4 C6 操作系统 C4，C7 C7 计算机组成原理 C2 例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业， 假设这些课程的名称与相应代号有如下关系： 2/29
课程之间的先后关系可用有向图表示：可以这样排课：C,-Cg-Cs-1-C3-C2-C4C2-C7-C1-C3C4-Cs-C6第1学期第2学期3/29
课程之间的先后关系可用有向图表示： C1 C3 C4 C2 C7 C6 C5 可以这样排课： C1-C3-C2-C4- C7-C6-C5 C2-C7-C1-C3- C4-C5-C6 第1学期 第2学期 3/29
拓扑排序的过程如下：（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它。（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边。（3）重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。4/29
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它。 （2）从图中删去该顶点，并且删去从该顶点发出的全部有向边。 （3）重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。 拓扑排序的过程如下： 4/29
拓扑排序的结果有两种：一种是图中全部顶点都被输出，即得到包含全部顶点的拓扑序列，称为成功的拓扑排序。另一种就是图中顶点未被全部输出，即只能得到部分顶点的拓扑序列，称为失败的拓扑排序。说明有向图中存在回路。5/29
拓扑排序的结果有两种： 一种是图中全部顶点都被输出，即得到包含全部顶点的拓扑序列， 称为成功的拓扑排序。 另一种就是图中顶点未被全部输出，即只能得到部分顶点的拓扑 序列，称为失败的拓扑排序。 说明有向图中存在回路。 5/29