拓扑排序

在这里我们引入AOV(Activity-On-Vertex)网,图的顶点代表活动,其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。


对于一个工程,我们首先将这个大工程分为很多小项目。例如学习计算机专业,我们要学习高等数学,大学英语,程序设计基础,c++,计算机网络,操作系统,计算机组成原理,编译原理。有的课程学习需要先学习完先导课程。

我们给每个科目编上编号:

高等数学  1

大学英语  2

程序设计基础  3

C++ 4

计算机网络  5

操作系统  6

计算机组成原理  7

编译原理  8


课程之前的关系是:

拓扑排序

要学习科目5,必须先学习完3与4才可以。

要学习科目8,必须先学习完6与7才可以。


这样就会产生两个序列:

12345678

12345768

这就是拓扑排序。