图论之拓扑排序思维导图

一个图能进行拓扑排序的充要条件是它是一个有向无环图(DAG)，有环图不能进行拓扑排序。

出度：以点u为起点的边的数量称为u的出度。

入度：以点v为终点的边的数量称为v的入度。

一个点的入度和出度体现了这个点的先后关系。如果一个点的入度等于0，则说明它是起点，是排在最前面的；若它的出度等于0，则说明它是排在最后面的。

基于BFS的拓扑排序有两种思路，即无前驱的顶点优先、无后继的顶点优先。

方法：先输出入度为0（无前驱，优先级最高）的点，操作如下，其中Q是BFS的队列。

步骤如下：

（1）找到所有入度为0的点，放进队列，作为起点，这些点谁先谁后没有关系。若找不到入度为0的点，说明这个图不是DAD，不存在拓扑排序。

（2）弹出队首a，a的所有邻居结点入度减1，把入度减为0的邻居结点放进队列，没有减为0的点不能放进队列。

（3）继续上述操作，直到队列为空。

队列输出，且包含了所有的点，这就是一个拓扑排序；若队列已空，但还有点没有入队，则这些点的入度都不是0，说明图不是DAG，不存在拓扑排序。

以上过程也可以反过来执行，从出度为0（无后继，优先级最低）的点开始，逐步倒推。

复杂度分析：初始化查找入度为0的点需检查每一条边，复杂度为O(E)；队列操作中每个点进出队列一次，需检查它直接连接的所有邻居，复杂度为O(V+E) 。总复杂度O(V+E)

回顾DFS深度搜索的原理，是沿着一条路径一直搜索到最底层，然后逐层回退。

一个有向无环DAG图，如果只有一个点u是0入度的，那么从u开始DFS，DFS递归返回的顺序就是拓扑排序（是一个逆序）。DFS递归返回的首先是最底层的点，它一定是0出度点，没有后继点，是拓扑排序的最后一个点；然后逐步回退，最后输出的是起点u；输出的顺序是一个逆序。

为了按正确的顺序打印出拓扑排序，可以使用栈stack来作为拓扑排序队列。