什么是拓扑排序?有向图存在拓扑序列的条件是什么?

核心考点

AOV网、拓扑排序定义、存在条件及入度法判定有环，重点掌握“有向无环图”这一充要条件。

参考答案(答题要点)

1.拓扑排序定义：对有向图的顶点排成一个线性序列，使得图中任意一条有向边(u,v)，在序列中顶点u都排在顶点v之前。这样的线性序列称为拓扑序列。

2.存在条件：有向图存在拓扑序列的充分必要条件是该有向图无环，即为有向无环图DAG。若图中存在回路，则回路上的顶点无法排出先后顺序，不存在拓扑序列。

3.入度法思想：每次选择一个入度为0的顶点输出，并删除该顶点及其所有出边，同时将相关顶点入度减1;重复直到全部顶点输出或没有入度为0的顶点。若输出顶点数小于总顶点数，说明图中有环。

4.复杂度与性质：邻接表存储时，拓扑排序时间复杂度为O(V+E)。拓扑序列不一定唯一;当某一步同时存在多个入度为0的顶点时，可产生不同拓扑序列。

5.总结：拓扑排序常用于AOV网中安排活动先后顺序。判断有向图能否拓扑排序，核心看是否有环;有环则无拓扑序列，无环则至少存在一个拓扑序列。

易错提醒

有向图连通不是存在拓扑序列的必要条件，孤立顶点也可排入序列。拓扑序列不唯一，不能默认答案只有一种。入度法若中途找不到入度为0的顶点，说明剩余部分有环。拓扑排序只适用于有向图，不用于无向图。

今日小测

一个有向图存在拓扑序列的充分必要条件是什么?

答案：该有向图无环，即为有向无环图DAG。