算法9拓扑排序.ppt

文档介绍：算法9拓扑排序
*
方案、施工过程、消费流程、程序流程等都是“工程〞。除了很小的工程外，一般都把工程分为假设干个叫做“活动〞的子工程。完成了这些活动，这个工程就可以完成了。
例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些那么不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。
*
例
课程代号 课程名称 先修棵
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
无
C1
C1,C2
C1
C3,C4
C11

C3,C6
无
C9
C9
C1,C9,C10
程序设计基础
离散数学
数据结构
汇编语言
语言的设计和分析
计算机原理
编译原理
操作系统
高等数学
线性代数
普通物理
数值分析
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
*
1、在AOV中
拓扑有序序列：将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。
拓扑排序——把AOV网络中各顶点按照它们互相之间的优先关系排列成一个线性序列的过程。
检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，假设网中所有顶点都在它的拓扑有序序列中，那么该AOV网必定不存在环。
二、拓扑排序
*
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8
或 ：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8
一个AOV网的拓扑序列不是唯一的
*
B
D
A
C
对于有向图
不能求得它的拓扑有序序列。
因为图中存在一个回路 {B, C, D}
*
输入AOV网络。有 n个顶点。
1 在AOV网络中选一个没有直接前驱的顶点，并输出之。
2 从图中删去该顶点, 同时删去所有它发出的有向边。
3 重复以上 1、2 步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。
a
b
c
g
h
d
f
e
a
b
h
c
d
g
f
e
没有前驱的顶点
删除顶点及以它为尾的弧
 弧头顶点的入度减1
a
b
c
g
h
d
f
e
需要设一个数组indegree[w]，记录顶点的入度数
 入度为零的顶点