图论算法引理1有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边
证明：→：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路
←：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边
设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻d[v]从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边
（证毕）
以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。
