有向圖遍歷演算法

『壹』 對連通圖進行一次先深遍歷可訪問圖的全部頂點，對嗎

圖的遍歷從圖中某一頂點出發，按某種搜索方法訪遍其餘頂點，且使每一頂點僅被訪問一次。這一過程稱為圖的遍歷。遍歷圖的基本搜索方法有兩種：深度優先搜索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);
}
}
}
}