想想现实生活中还有哪些拓扑应用
拓扑排序
信息工程系 xxx
数据结构之
拓扑排序
信息工程系
xxx
案例 教学计划的编制
课程代号
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
12
课程名称
程序设计基础 离散数学 数据结构 汇编语言
语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析
34 5
先修课
无 C1 C1,C2 C1 C3,C4 C11 C3.C5 C3,C6 无 C9 C9 C1,C9,C10
因此，对给定的AOV网络，必须先判断它是否存在有
向环。
何谓拓扑排序呢？
拓扑排序
3
定义
按照有向图给出的次序关系，将图中顶点 排成一个线性序列，对于有向图中没有限 定次序关系的顶点，则可以人为加上任意 的次序关系。由此所得顶点的线性序列称 之为拓扑有序序列
如何进行拓扑排序呢！
拓扑排序
4
方法
在AOV网络中选一个没有直接前驱的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的 有向边; 重复以上 、 步, 直到
怎么合理 安排教学 计划呢
6
7
8
9
拓扑排序将会给你想要的答案
案例
C4
C2
C1
C3
课程代号
C1
C2
C3
C4
C5
C6
C7
C8
C9
C5
C10
C11
C12
C7
课程名称
先修课
程序设计基础 无 离散数学 C1 数据结构 C1,C2 汇编语言 C1
语言的设计和分析 C3,C4 计算机原理 C11 编译原理 C3.C5 操作系统 C3,C6 高等数学 无 线性代数 C9 普通物理 C9 数值分析 C1,C9,C10
C12 C8
C9 C10
C6
表示课程之间优先关系的AOV网
C11 1
知识点
2
AOV网
可 以用有向图表示一个工程。在这种有向图中，用顶
点表示 活动，用有向边<Vi, Vj>表示活动间的优先关系。 Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活 动的AOV网络(Activity On Vertices)。
--C10--C11--C6—C1C28—C8
C9
C10
C6
C11
1
7
拓扑排序
2
7
1
5
9
3
8
4
6
思考：如何实现该图的拓扑排序
7
拓扑排序
4
注意事项
全部顶点均已输出，拓扑有序序列形成，拓扑 排序完成；或图中还有未输出的顶点，但已跳 出处理循环。这说明图中还剩下一些顶点，它 们都有直接前驱，再也找不到没有前驱的顶点 了。这时AOV网络中必定存在有向环。
全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或
图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点， 它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存 在有向环。
得到相关结果
1
5
C2
C1
C3
C7
拓扑序列：C1C1-2-C2--C3--C4--C5--C7--C9