第22章 图的基本算法 22.4 拓扑排序

# 一、综述 定义：对有向无回路图G=(V,E)进行须拓扑排序后，结果为该图所有顶点的一个线性序列，满足如果G包含边(u, v)，则在该序列中，u就出现在v的前面（如果图是有回路的，就不可能存在这样的线性序列）。 定理：一个有向图G是无回路图，当且仅当对G进行深度优先搜索时没有得到反向边。 # 二、代码 https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/section22_4.cpp # 三、练习 ### 22.4-1 t q u z w x v y r m s o n p ### 22.4-2 书上给的结果不对，psryv不通，因此是3条通路。 https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/Exercise22_4_2.cpp ### 22.4-3 回路即反向边，只要不存在反向边，就没有回路 ### 22.4-5 [算法导论-22.4-5-用队列实现拓扑排序](http://blog.csdn.net/mishifangxiangdefeng/article/details/7840091)