文档介绍：会计学
1
算法(suàn fǎ)拓扑排序
第一页，共47页。
第2页/共47页
第二页，共47页。
3
计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。
例如，计算机专业学生的学****就是一个工程，每一门课程的学****就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先(lǐnɡ xiān)关系，有的课程可以并行地学****br/>第3页/共47页
第三页，共47页。
4
例
课程代号 课程名称 先修棵
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
第4页/共47页
第四页，共47页。
5
1、在AOV中
拓扑有序序列：将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。
拓扑排序(pái xù)——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。
检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。
二、拓扑(tuò pū)排序
第5页/共47页
第五页，共47页。
6
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
拓扑(tuò pū)序列：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ù shi)唯一的
第6页/共47页
第六页，共47页。
7
B
D
A
C
对于(duìyú)有向图
不能求得它的拓扑(tuò pū)有序序列。
因为图中存在一个(yī ɡè)回路 {B, C, D}
第7页/共47页
第七页，共47页。
8
输入AOV网络。有 n个顶点。
1 在AOV网络中选一个没有直接前驱的顶点，并输出之。
2 从图中删去该顶点, 同时(tóngshí)删去所有它发出的有向边。
3 重复以上 1、2 步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。
第8页/共47页
第八页，共47页。
a
b
c
g
h
d
f
e
a
b
h
c
d
g
f
e
没有前驱的顶点(dǐngdiǎn)
删除顶点(dǐngdiǎn)及以它为尾的弧
弧头顶(tóudǐng)点的入度减1
a
b
c
g
h
d
f
e
需要设一个数组indegree[w]，记录顶点(dǐngdiǎn)的入度数
入度为零的顶点
第9页/共47页
第九页，共47页。
10
3、AOV网络的存储方式(fāngshì)--邻接表表示
C0
C1
C2
C3
C4
C5
C0
C1
C2
C3 0
C4
C5 0
0
1
2
3
4
5
ind data firstarc
1
3
0
1
0
3
1
adjvex next
3 0
5
1
5 0
0
1
5 0
第10页/共47页
第十页，共47页。