拓扑排序
在这里我们引入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
这就是拓扑排序。