文档介绍：数据结构与算法
1
Chapter 10
图--2
2
拓扑排序
对于拓扑分类的研究，主要涉及的数据结构是无环路有向图。
不存在有向环路的有向图简称为无环路有向图。
1
2
3
4
无环路有向图
1
2
3
4
有环路有向图
3
拓扑排序
计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。
例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。
4
C1 高等数学
C2 程序设计基础
C3 离散数学 C1, C2
C4 数据结构 C3, C2
C5 高级语言程序设计 C2
C6 编译方法 C5, C4
C7 操作系统 C4, C9
C8 普通物理 C1
C9 计算机原理 C8
C1
C8
C9
C7
C3
C4
C2
C5
C6
学生课程学习工程图
5
拓扑排序和AOV网络
可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边<Vi, Vj>表示活动的关系。Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)。
在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边<Vi, Vj>，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。
因此，对给定的AOV网络，必须先判断它是否存在有向环。
6
拓扑排序和AOV网络
检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前导和后继关系都能得到满足。
这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑分类，也叫拓扑排序。
如果通过拓扑分类能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。
7
给定一个无环路有向图G=(V,E) , 各结点的编号为v=(1,2, …,n)。要求对每一个结点 i 重新进行编号，使得若 i 是 j 的前导，则有label[i]<label[j]。即拓扑分类是将无环路有向图排成一个线性序列，使当从结点 i 到结点 j 存在一条边，则在线性序列中，将 i 排在 j 的前面。
C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或
C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6
C1
C8
C9
C7
C3
C4
C2
C5
C6
8
输入AOV网络。令 n 为顶点个数。
在AOV网络中选一个入度为0的顶点, 并输出之;
从图中删去该顶点, 同时删去所有它发出的有向边;
重复以上 1、2 步, 直到
全部顶点均已输出，拓扑有序序列形成，拓扑分类完成；或
图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前导，再也找不到入度为0的顶点了。这时AOV网络中必定存在有向环。
拓扑排序算法
9
拓扑分类的过程--1
(a)无环有向图
(b)输出顶点4
(c)输出顶点0
(d)输出顶点3