Question

设计一个基于深度优先遍历的算法，判断一个给定的有向图是否包含回路。

Answer 1

你好，关于DFS判断有向图是否存在回路的问题，我本人编写的考研资料中有相关的原创总结，希望对你有帮助，转载还请注明原创出处：《大连理工大学软件学院887专业课（2021版）》。如有问题可以加我QQ601964408交流。
法一：利用递归方式，在DFS对图进行遍历时，将遍历过的顶点放入栈中，如果新遍历的顶点已经存在于递归栈中，则说明存在一个反向边，即存在一个环。此时栈中结点刚好是环路中的所有结点！
注意该方法没办法用DFS的非递归方法实现，因为非递归方法中，利用出栈的结点获取下一个邻接点入栈，和递归方式不同的地方在于，即使图中有环，非递归方法中的栈也无法存储环上的结点。（DFS的非递归详见本小结后续的代码总结部分）
代码实现如下：
void HasCycle ( Graph G ) {
bool visited [MAX_VERTEX_NUM] ; //访问标记数组
bool recursionStack [MAX_VERTEX_NUM] ; //标记该点是否在栈中
for ( i=0 ; i<G.vexnum ; i++) {
//mark all the vertices as not visited and not part of recursion stack
//标记所有结点均未访问以及不在栈中
visited [i] = FALSE ;
recursionStack [i] = FALSE ;
}
//call the recursive helper function to detect cycle in different DFS trees
//调用辅助递归函数以检测不同DFS树种的环路
for ( int i =0 ; i < G.vexnum ; i++ ) //每次检测一个连通图
if ( CheckCyclic ( G , i , VISITED , recursionStack ) ) ;
return true ; //存在回路
return false ; //不存在回路
}

bool CheckCyclic ( Graph G , int v , bool [ ] visited , bool [ ] recursionStack ) {
if ( visited [v] == FALSE) {
//mark the current nodes as visited and part of recursion stack
//将当前结点的标记数组和递归栈标记，置为已访问
visited [v] = TRUE ;
recursionStack [v] = TRUE ;

//recursion for all the vertices adjacent to this vertex
//递归该顶点附近的所有顶点
for ( Edge e = G.FirstEdge(v) ; G.IsEdge(e) ; e=G.NextEdge(e) ) {
//判断下一结点未被访问，进入递归函数判断是否有环
if ( visited [G.ToVertex(e) ] == FALSE &&
CheckCyclic ( G , G.ToVertex(e) , visited , recursionStack) )
return TRUE ;
//当下一结点已经访问过，并且已经在栈中，判断有环
else if ( recusionStack (G.ToVertex(e) ) == TRUE )
return TRUE ;
}//end_for
}//end_if

//remove the vertex from recursion stack
//从递归栈种移除该结点
recursionStack [v] = FALSE ;
return false ; //判断无环
}
--------------------------------------------------------------------------------------------------
法二：本方法与法一非常相似，方法一中存在三种情况，还未入栈时表示未被访问过的点；在栈中时表示已经被访问过但是还没有递归结束；从栈中出栈时表示递归结束，即后代也全部被访问过了。上述三种情况分别用 -1，0，1三种状态来标记点。
针对上述思路，假设正在处理点v，那么v的状态是0，其余正在处理的结点的状态也是0，如果从状态0的结点遍历到状态为0的结点，那么就存在环。此时所有状态为0的结点构成了一个环！发现存在环时遍历输出state数组即可，不过该方法输出时不是按照环路的顺序输出；如果需要顺序输出环路，可增加一个cycle数组，每次记录环路的起点位置i。用cycle[i]记录结点i的下一个结点编号。利用递归的方式输出cycle数组即可得到回路顺序。
代码实现：
bool Found = FALSE ; //标记是否发现环路
void HasCycle ( Graph G ) {
int state [MAX_VERTEX_NUM] ; //结点状态标识数组
for ( i=0 ; i<G.vexnum ; i++) {
state [i] = -1 ;
}
for ( int i =0 ; i < G.vexnum ; i++ ) { //每次检测一个连通图
CheckCyclic ( G , i , state )；
if ( Found == TRUE ) ; //存在回路
return true ;
}
return false ; //不存在回路
}

void CheckCyclic ( Graph G , int v , int [ ] state ) {
if ( state [v] == -1) { //如果未访问过
state [v] = 0 ; //改变该点的状态
for ( Edge e = G.FirstEdge(v) ; G.IsEdge(e) ; e=G.NextEdge(e) ) {
if ( state [ G.ToVertex(e) ] == -1 )
CheckCyclic ( G , G.ToVertex(e) , state )
else if ( state [ G.ToVertex(e) ] == 0 ) //该图有环
Found = TRUE ;
}//end_for
}//end_if

state [v] = 1 ; //该点递归结束，即后代也访问完
}