DFS與BFS——理解簡單搜尋(中文虛擬碼+例題) | IT人

深度優先搜尋演算法（Depth First Search）：一種用於遍歷或搜尋樹或圖的演算 ... 每個節點被訪問後被踹出，為了程式碼的簡潔易懂，使用了c++的stl。

Togglenavigation IT人 IT人 DFS與BFS——理解簡單搜尋(中文虛擬碼+例題) Simon5ei發表於 2020-07-27 新的方法和概念，常常比解決問題本身更重要。

————華羅庚 引子 深度優先搜尋（DeepFirstSearch）廣度優先搜尋（BreathFirstSearch）當菜鳥們（比如我）初步接觸演算法的時候，會接觸這兩種簡單的盲目搜尋演算法，相較與其他眾多的演算法，這兩種演算法相對較好理解，運用範圍也很廣，在眾多的學科競賽裡都可以見到它們的影子，話不多說，我們開始。

深度優先搜尋（DeepFirstSearch） 深度優先搜尋演算法（DepthFirstSearch）：一種用於遍歷或搜尋樹或圖的演算法。

沿著樹的深度遍歷圖的節點，儘可能深的搜尋圖的分支。

當節點v的所在邊都己被探尋過或者在搜尋時結點不滿足條件，搜尋將回溯到發現節點v的那條邊的起始節點。

整個程式反覆進行直到所有節點都被訪問為止。

屬於盲目搜尋,最糟糕的情況演算法時間複雜度為O(!n)。

做一個形象的比喻，dfs好比走迷宮，得一直走到頭，看看路的盡頭是不是出口，如果是，就直接走出去，如果不是，那就返回上一個“標記點”尋找不一樣的可行方法。

dfs的實現關鍵在於回溯，這個可以用兩種方法實現（遞迴、堆疊），以下給出虛擬碼 遞迴實現： 遞迴實現是dfs最廣泛的使用方法。

voiddfs(intx,inty) { if(達到出口||無法繼續) { 相應操作; return； } if（對應x方向的下一步可以繼續） { 新增標記;//給該位置記上標記，如果後續遞迴呼叫碰到了這個點，則該方向不能繼續下一步 dfs(x+1,y);//呼叫遞迴 取消標記;//上一步對應的遞迴操作全部結束，則要取消標記對後續操作的影響 } elseif（對應y方向的下一步可以繼續）{ 新增標記; dfs(x,y+1); 取消標記; } } 棧實現： 棧實現的基本思路是將一個節點所有未被訪問的“鄰居”（即“一層鄰居節點”）壓入棧中“待用”，然後圍繞頂部節點進行判定，每個節點被訪問後被踹出，為了程式碼的簡潔易懂，使用了c++的stl。

voiddfs_stack(intstart,intn){ stacks;//建立棧 for(inti=0;i #defineLLlonglong #defineINF0x3f3f3f3f usingnamespacestd; intLeft,Right,minn,ans=0; ints[5]; inta[21][5]; voiddfs(intx,inty){ if(x>s[y]){//任務全部分配完畢，做最後處理 minn=min(minn,max(Left,Right)); return; } Left+=a[x][y];//任務丟給左腦(標記) search(x+1,y); Left-=a[x][y];//把左腦的任務抽出給右腦（取消標記） Right+=a[x][y];//任務丟給右腦(標記) search(x+1,y); Right-=a[x][y];//把右腦的任務抽出給左腦（取消標記） } intmain(){ cin>>s[1]>>s[2]>>s[3]>>s[4]; for(inti=1;i<=4;i++){//減少碼量 Left=Right=0; minn=INF; for(intj=1;j<=s[i];j++) cin>>a[j][i]; dfs(1,i);//分別對4門科目深搜； ans+=minn; } cout<//stl的queue容器 queuequ;//建立佇列 voidbfs(起始狀態){ while(未到達最終狀態){ if(起始狀態向x方向可走) qu.push(起始狀態+x);//該狀態入隊 if(起始狀態向y方向可走) qu.push(起始狀態+y);//該狀態入隊 ………………… while(!qu.empty()){//當佇列非空 處理(隊頂)qu.top(); 相應操作； qu.pop();//隊首彈出隊 }//一次迴圈結束，執行下一次迴圈 } } 例題理解OpenJ_Bailian-2790迷宮 題目背景 一天Extense在森林裡探險的時候不小心走入了一個迷宮，迷宮可以看成是由n*n的格點組成，每個格點只有2種狀態，.和#，前者表示可以通行後者表示不能通行。

同時當Extense處在某個格點時，他只能移動到東南西北(或者說上下左右)四個方向之一的相鄰格點上，Extense想要從點A走到點B，問在不走出迷宮的情況下能不能辦到。

如果起點或者終點有一個不能通行(為#)，則看成無法辦到。

Input 第1行是測試資料的組數k，後面跟著k組輸入。

每組測試資料的第1行是一個正整數n(1<=n<=100)，表示迷宮的規模是n*n的。

接下來是一個n*n的矩陣，矩陣中的元素為.或者#。

再接下來一行是4個整數ha,la,hb,lb，描述A處在第ha行,第la列，B處在第hb行,第lb列。

注意到ha,la,hb,lb全部是從0開始計數的。

Output k行，每行輸出對應一個輸入。

能辦到則輸出“YES”，否則輸出“NO”。

SampleInput 2 3 .## ..# #.. 0022 5 ..... ###.# ..#.. ###.. ...#. 0040 SampleOutput YES NO AC程式碼 #include #definemod1000000007 #defineeps1e-6 #definelllonglong #defineINF0x3f3f3f3f #defineMEM(x,y)memset(x,y,sizeof(x)) usingnamespacestd; intT,n,m; intsx,sy,ex,ey;//初始位置結束位置 charmp[1005][1005];//原始地圖 intdt[][2]={{1,0},{-1,0},{0,1},{0,-1}};//方向 structnode { intx,y;//橫縱座標 }; nodenow,net; voidbfs() { intf=0; queueq; now.x=sx,now.y=sy; mp[now.x][now.y]='#';//這裡走過變'.'為'#'即可 q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(now.x==ex&&now.y==ey)//到達終點 { f=1; cout<=0&&net.x=0&&net.y>T; while(T--) { cin>>n; for(inti=0;i>mp[i][j]; cin>>sx>>sy>>ex>>ey; //cout<