有向图遍历算法

‘壹’ 对连通图进行一次先深遍历可访问图的全部顶点，对吗

图的遍历从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。这一过程称为图的遍历。遍历图的基本搜索方法有两种：深度优先搜索DFS（Depth First Search）和广度优先搜索BFS（Broad First Search）。这两种方法都适用于有向图和无向图。图的遍历算法设计需要考虑3个问题： （1）图的特点没有首尾之分，所以算法的参考要指定访问的第一个顶点。 （2）对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能的回路问题。 （3）一个顶点可能和若干个顶点都是想邻顶点，要使一个顶点的所有想邻顶点按照某种次序被访问。对于连通图，从初始顶点出发一定存在路径和图中的所有其他顶点相连，所以对于连通图从初始顶点出发一定可以遍历该图。图的深度优先遍历图的深度优先遍历DFS算法是每次在访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这样的算法是一个递归算法。 1.连通图的深度优先遍历算法思想。（1）访问初始顶点v并标记顶点v已访问。（2）查找顶点v的第一个邻接顶点w。（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。【例】 现以图 7.9 （ a ）为例说明深度过优先搜索过程。假定 v 1 是出发点，首先访问 v 1 。因 v 1 有两个邻接点 v 2 、 v 3 均未被访问过，可以选择 v 2 作为新的出发点，访问 v 2 之后，再找 v 2 的未访问过的邻接点。同 v 2 邻接的有 v 1 、 v 4 、 v 5 ，其中 v 1 已被访问过，而 v 4 、 v 5 尚未被访问过，可以 v 4 选择作为新的出发点。重复上述搜索过程，继续依次访问 v 8 、 v 5 。访问 v 5 之后，由于与 v 5 相邻的顶点均已被访问过，搜索退回到 v 8 。由于 v 8 、 v 4 、 v 2 都是已被访问的邻接点，所以搜索过程连续地从 v 8 退回到 v 4 ， 再退回到 v 2 ，最后退回到 v 1 。这时选择 v 1 的未被访问过的邻接点 v 3 ，继续往下搜索，依次访问 v 3 、 v 6 、 v 7 ，从而遍历了图中全部顶点。

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

你好，关于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 ; //该点递归结束，即后代也访问完
}

‘叁’ 对连通图进行一次先深遍历可访问图的全部顶点，对吗

如果是无向的连通图或者有向的强连通图,是对的,对于无向的非连通图就不可能一次遍历访问到所有顶点了,对于有向的非强连通图则有可能对,有可能不对

‘肆’ 图遍历的算法

图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。 深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //访问标志数组初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G
visited[v]=TRUE; VisitFunc(v); //访问第v个顶点
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
//若w是v的最后一个邻接点，则返回空（0）。
if(!visited[w])
DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS
} 图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空辅助队列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入队列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //队头元素出队并置为u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w为u的尚未访问的邻接顶点
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}