dfs非遞歸java（DFS非遞歸算法）

本文目錄一覽：

• 1、DFS 遞歸為什麼比非遞歸要快？？？
• 2、設計一個基於深度優先遍歷的算法，判斷一個給定的有向圖是否包含迴路。
• 3、如何將回溯法dfs改寫為非遞歸的
• 4、數據結構圖的遍歷 1)先任意創建一個圖； 2)圖的DFS,BFS的遞歸和非遞歸算法的實現 3)要求用有向圖和無向圖

DFS 遞歸為什麼比非遞歸要快？？？

非遞歸肯定要快一些，遞歸的話需要不斷的調用自己的函數原型，每調用一次都需要增長棧來存儲變量，而且返回前還需要將當前結果寫入在返回地址中，對內存使用效率極低。

設計一個基於深度優先遍歷的算法，判斷一個給定的有向圖是否包含迴路。

你好，關於DFS判斷有向圖是否存在迴路的問題，我本人編寫的考研資料中有相關的原創總結，希望對你有幫助，轉載還請註明原創出處：《大連理工大學軟件學院887專業課（2021版）》。如有問題可以加我QQ601964408交流。

法一：利用遞歸方式，在DFS對圖進行遍歷時，將遍歷過的頂點放入棧中，如果新遍歷的頂點已經存在於遞歸棧中，則說明存在一個反向邊，即存在一個環。此時棧中結點剛好是環路中的所有結點！

注意該方法沒辦法用DFS的非遞歸方法實現，因為非遞歸方法中，利用出棧的結點獲取下一個鄰接點入棧，和遞歸方式不同的地方在於，即使圖中有環，非遞歸方法中的棧也無法存儲環上的結點。（DFS的非遞歸詳見本小結後續的代碼總結部分）

代碼實現如下：

void HasCycle ( Graph G ) {

bool visited [MAX_VERTEX_NUM] ; //訪問標記數組

bool recursionStack [MAX_VERTEX_NUM] ; //標記該點是否在棧中

for ( i=0 ; iG.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 ; iG.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 ; //該點遞歸結束，即後代也訪問完

}

如何將回溯法dfs改寫為非遞歸的

我的印象中貌似回溯法本身就是基於dfs的算法，俗稱爆搜？

可以寫人工棧，但是如果在競賽中的話寫人工棧意義不大，Linux下本身就有80W左右的棧空間，而且人工棧不見得就比系統的快。

人工棧的原理非常簡單，就是開若干個數組，每個數組對應開一個指針t，把原來dfs中每一層的信息都記錄到數組裡，dfs改成循環，如while (t!=0) ，要進入一層時t++，當退出一層時t–即可。

數據結構圖的遍歷 1)先任意創建一個圖； 2)圖的DFS,BFS的遞歸和非遞歸算法的實現 3)要求用有向圖和無向圖

//DFS,無向圖+有向圖，鄰接矩陣實現。

//你的東西太多了。一個一個問吧。而且200分太少了。你這麼多種情況。至少也得寫8種吧。

#include string

#include string.h

#include stdio.h

#include vector

#include iostream

#include set

#include math.h

#include map

#include algorithm

#include queue

using namespace std;

const int MAX=210000;

int mat[10][10];

bool vis[10]={false};

void DFS(int s,int n)

{

int i;

vis[s]=true;

printf(“%d “,s);

for(i=0;in;i++)

{

if(mat[s][i]!vis[i])

{

DFS(i,n);

}

}

}

int main()

{   

int i,n;

int j;

n=10;

for(i=0;in;i++)

{

for(j=0;jn;j++)

mat[i][j]=1;

}

DFS(0,n);

    return 0;

} 

/*

*/