dfs與bfs的簡單總結及應用 - 台部落
文章推薦指數： 80 %
dfs與bfs的簡單總結及應用 ... (1)：深度優先搜索（Depth-First-Search）是搜索算法的一種。
是沿着樹的深度遍歷樹的節點，儘可能深的搜索樹的分支。
當節點v ...
請輸入正確的登錄賬號或密碼
註冊
忘記密碼
首頁
未分類
正文
dfs與bfs的簡單總結及應用
原創
溺生
2019-03-0403:12
本來想昨晚總結一下的，但是不小心玩起了遊戲，當作放鬆一下了，現在我們進入正題：
一、dfs的簡要說明
(1)：深度優先搜索（Depth-First-Search）是搜索算法的一種。
是沿着樹的深度遍歷樹的節點，儘可能深的搜索樹的分支。
當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。
這一過程一直進行到已發現從源節點可達的所有節點爲止。
如果還存在未被發現的節點，則選擇其中一個作爲源節點並重復以上過程，整個進程反覆進行直到所有節點都被訪問爲止。
屬於盲目搜索。
(2)：DFS是圖論裏面的一種搜索算法，他可以由一個根節點出發，遍歷所有的子節點，進而把圖中所有的可以構成樹的集合都搜索一遍，達到全局搜索的目的。
所以很多問題都可以用dfs來遍歷每一種情況，從而得出最優解，但由於時間複雜度太高，我們也叫做暴力搜索。
(3)：DFS如同數據結構中的棧結構，是屬於一種後進先出的結構，比如說一個羽毛球筒，把它裝滿之後，我們開始使用時，拿的總是最後放進去的那一個。
所以這就導致了所有的點進入棧時有一個順序，我們稱之爲：DFS序。
(4)：根據dfs的英文全寫，我們可以知道這是一種深度優先搜索的搜索算法，什麼叫做深度優先？意思就是它搜索一顆子樹時，它要遍歷到底纔會“回頭”，比如說：上有向圖中的搜索模式爲(以DFS序來描述)：a->b->e->b->f->c->f->b->c->b->a->c->a->d->g->d->a，有人就會問爲什麼搜索到c的時候不搜索a呢？因爲我們假設的這是一個有向圖。
而且我們可以看到如果你面對的圖是一個無向圖，這個時候這個樹將會持續搜索因爲可能會形成環路，使得棧的結構一直進進出出，導致程序崩潰，所以我們也因該注意，在寫DFS時，如果面對的是一個無向圖的話我們需要進行標記。
一般的標記方法有:①這個點的父節點被標記，使得子節點不能回到父節點造成循環②訪問過的節點被標記。
這兩種方法視情況而定。
(5)：對於暴搜來說，因其複雜度太高，我們就會想去優化它的複雜度，這一過程稱爲剪枝，剪紙分爲可行性剪枝和最優化剪枝，關於剪枝引申出一種名爲記憶化搜索的方法，該方法與動態規劃類似。
(對於剪枝來說，我自己也是不太精通，剛入編程界半年，以後搞懂必會寫總結)。
二、BFS的簡要說明
(1)：與DFS相對的那就是BFS了，BFS稱爲寬度優先搜索也叫做廣度優先搜索，他是按層遍歷每一種狀態的下一種狀態。
搞不懂？沒關係我們來看一下一個例題：
給你一個整數X，問是否存在一個這樣一個數字A：①這個數字是X的倍數②這個數字僅由0與1這兩種數字組成例如X=2，A=10。
這個題當然可以用DFS來做，我們以1爲起點這樣就成了一個01二叉樹，意思就是說每一種情況我們都可以有兩種選擇要麼添0，要麼在後面添1。
所以我們可以寫出代碼：
voiddfs(intstart)
{
if(A%X==0)//這是我們搜索結束的條件
{
ans=A;//讓ans記錄答案開始return
return;
}
dfs(start*10);
dfs(start*10+1);
}
這樣我們就完成了搜索，起始量爲1搜先1會變成10，11，然後10會變成100和101，11變成110與111。
我們這就完成了所有的情況遍歷，當A%X==0時我們記錄最後的答案。
所以我們開始試例子：輸入2按照dfs序的話，首先不符合條件，然後進入下一步搜索，X*10=10，發現10%2==0，然後開始返回ans記錄A，這就是最後答案，但是你會發現程序崩潰了。
我們分析一下原因：DFS爲深度優先搜索，所以我們的左子樹可以看作是在末尾加0，然後右子樹可以看作在末尾加1，所以這樣就形成了一棵樹。
按照DFS我們的意圖是讓他搜索左子樹，所以在左子樹中找到了滿足條件的數：10。
但是爲什麼程序會崩潰呢？
因爲搜索到樹之後，按照我們剛剛的DFS序，這個樹遍開始回溯(你可以想象成這棵樹開始回縮)，每回溯到一個節點，因爲這個節點的右子樹還沒有搜索，所以會再去搜索這個節點的右子樹，但是這個節點的右子樹是在末尾進行加1，而末尾是1絕對不可能是2的倍數所以這個樹會一直按照往右子樹搜索的趨勢進行下去，導致程序崩潰。
(2)：那是不是這個問題只能枚舉了呢？其實DFS是可以的，在網絡大神的果斷判斷之下這個問題出了一個新解：當搜索的深度爲19時，此時的答案一定會出現，這時候回溯就好了。
所以說我們加一個step記錄深度就可以了：
voiddfs(intstart,intstep)
{
if(A%X==0&&step==19)//這是我們搜索結束的條件
{
ans=A;//讓ans記錄答案開始return
return;
}
dfs(start*10,step+1);
dfs(start*10+1,step+1);
}
(3)：還有沒有更好的方法呢？在考慮這個問題的時候我們回顧一下剛剛爲什麼程序崩潰，原因就是因爲DFS是一個深度優先搜索，他每次必須要深搜到底，所以對於末尾是1來說永遠沒有結束條件所以它一直會搜索下去！這個時候我們可不可以想有沒有這樣一種搜索模式，出現A=10這個情況之後我們立刻停止就可以了呢？當然是有的，那就是BFS。
(4)：弄完上面這個例題，也就真正的引出了BFS也發現了DFS的一些小缺點。
下面說一下上面留下的定義：按層遍歷每一種的狀態的下一種狀態。
首先BFS是與數據結構中的隊列相似，隊列是一種先進先出的結構，這又比如說你把一些水果按時間一天一個放進一個箱子裏，但這些水果時間長了會變質，我們假設變質日期是一樣的，那麼你每次拿都是拿的最早放進去的那個。
我們來看一下它的搜索模式：
BFS的訪問過程與圖中序號一致
如果我們按照BFS順序搜索，就會時上圖的樣子，首先把根節點1放進去，然後把他的3個子節點放入隊列之中，然後第一個再把第一個進入隊列的子節點的三個子節點放入對列中，然後再去訪問第二個放入隊列的也就是上圖中的3號點，所以我們看到這個過程是一層層的搜索，把這一層所有的情況搜索一遍，又把這一層所有狀態對應的下一種狀態入隊列，這樣一步步搜索完成。
(4)：所以說對於剛剛那個題目而言，我們如果按層遍歷就不會出現程序崩潰的現象，比如說第二層有1011，那我們就不必搜索下一層了。
因爲這一層裏面已經有我們想要的答案了。
具體僞代碼：
1入隊列
取出當前隊列的首元素，用一個值記錄，然後扔掉。
符合要求？跳出循環：繼續狀態搜索
把該元素對應的兩種狀態入隊列（+0，+1）
三、DFS的應用
(1).DFS由於有回溯的步驟，所以我們可以對其進行更新，比如並查集合並時的狀態壓縮都是使用DFS，還有圖論中的tarjan算法，lca等等。
(2)：搜索有狀態約束的問題，比如說：
在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有區別。
要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請編程求解對於給定形狀和大小的棋盤，擺放k個棋子的所有可行的擺放方案C。
Input
輸入含有多組測試數據。
每組數據的第一行是兩個正整數，nk，用一個空格隔開，表示了將在一個n*n的矩陣內描述棋盤，以及擺放棋子的數目。
n<=8,k<=n
當爲-1-1時表示輸入結束。
隨後的n行描述了棋盤的形狀：每行有n個字符，其中#表示棋盤區域，.表示空白區域（數據保證不出現多餘的空白行或者空白列）。
Output
對於每一組數據，給出一行輸出，輸出擺放的方案數目C（數據保證C<2^31）。
SampleInput
21
#.
.#
44
…#
…#.
.#…
#…
-1-1
SampleOutput
2
1
題目要求：棋子只能放在#上並且k個棋子必須在不同行不同列，所以說這裏進行了狀態的限制，我們如果用BFS做肯定不太好做，但是我們剛好可以運用DFS的回溯特點做這個題目;
因爲這個題目是二維的題目我們無法判斷該行該列到底有沒有放棋子，我們只可以判斷我們當前到的這一行放棋子了沒有，於是我們在外面加一個數組VIS，它標記着第i列有沒有放棋子，如果第i列放了棋子，那麼我們就令vis[i]==true。
然後我們dfs他的每一行，在其間遍歷他的每一列具體可能說不太清楚，我把代碼和註釋附上：
boolvis[50];
intn,k;
charmp[50][50];//標記每一列
/*AshGuang的版權*/
llcnt=0;
voiddfs(intx,intway)//用way記錄我們放了多少棋子
{
if(way==k)
{
cnt++;//cnt記錄方案數
return;//一定記得要return
}
if(x>=n)return;//這是判界因爲我們按行遍歷，一共有n行不能多出去
for(inti=0;i
(2)：求迷宮最短路，這種題目用DFS也是可以解的，用DFS的思路:有許多條路可以到達終點我們求一下到達終點的最小值。
這樣是非常耗時間的而BFS不一樣因爲BFS是按層遍歷，所以每一層對於根節點來說距離一定是最小的，不需要再次更新，我們到達終點時這個距離一定一定是最小的，比如說：
還是拿這張圖來說讓我們求到達的C的最小距離，按照BFS的思路，第二層就可以到C我們直接break就可以了，爲什麼？因爲如果a->b-f->c一定不會比直接到c近，這就是BFS最特殊的性質，在搜索過程中保留了最短路。
所以我們用一個輔助數組來標記記錄到當前節點的最小距離，如果f還要訪問c時，判斷一下如果c這個地方的距離已經被更新，說明它已經確定了最小值，後來的無法更新，我們就不讓c進入隊列。
這樣一來最小值也就確定了。
拿一個例題來說，1代表牆壁，0代表可通路每次可以向四個方向出發，起點在左上方，終點在右下方，問最短距離：
僞代碼：(用num[i][j]表示第i行第j個位置走過沒有)
因爲初始起點需要走0步，我們把num數組初始-1，mem(num,-1)；
左上角爲起點：
num[1][1]=0;
11進入隊列
取出當前隊列第一個元素(因爲二維通常需要使用結構體)
判斷它是否爲終點位置？break：continue；
遍歷該點四個方向可行方向
if(num[mx][my]==-1)
num[mx][my]=num[i][k]+1
把這個點進入隊列。
結束
具體代碼：
intbfs()
{
queue
if(num[mx][my]==-1&&str[mx][my]==0)//這裏還需要加一個判界，我就不手寫了有點累了。
{
num[mx][my]=num[u.x][u.y]+1;
q.push({mx,my});
}
}
}
}
(3)：同時移動性題目問題，火山在噴發，你在跑問是否可以跑出去。
詳情之前解釋過這個問題：Fire！
(4)：倒水問題，每次倒水狀態之間的轉移，之前也有過例題：非常可樂！&&POJ341pots
(5)：路徑還原，問從一個點到另一個點的最短路徑是多少，而題目不要求你輸入最短距離，而是要求你還原路徑這種時候通常需要加一個結構體數組來記錄，其實上面的例題pots也是一個路徑還原的問題，用一個簡單的例題總結一下路徑還原：
定義一個二維數組：
intmaze[5][5]={
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
它表示一個迷宮，其中的1表示牆壁，0表示可以走的路，只能橫着走或豎着走，不能斜着走，要求編程序找出從左上角到右下角的最短路線。
輸出;
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
我們定義結構體要加一個pre，記錄它是由哪個點轉移過來的：
#include
}
}
}
輸出時：只需要判斷對應下標的數組裏面存的是x==1&&y==1就好了。
用回溯寫：
voidprint(inta)
{
if(q[a].x==1&&q[a].y==1)
{
printf("(%d,%d)\n",q[a].x-1,q[a].y-1);
return;
}
else
{
print(q[a].pre);
printf("(%d,%d)\n",q[a].x-1,q[a].y-1);
}
}
五、總結
1.到這裏dfs與bfs的簡要介紹與總結也就寫完了，如果具體還不懂可以在下方留言，歡迎及時交流。
2.任何有關侵犯版權問題，我都會及時道歉，謝謝寬容。
3.BFS與dfs各自都有優點，具體問題我們具體分析。
4.DFS的樹的深度如果過長的話考慮用BFS而不去用DFS。
人一我百，人十我萬！加油！碼農！
發表評論
登录
所有評論
還沒有人評論，想成為第一個評論的人麼?請在上方評論欄輸入並且點擊發布.
相關文章
發佈一款座標轉換軟件
今天是西安市本土疫情爆發以來，居家隔離的第二天。
原本的工作節奏全都發生了改變，彷彿回到了2020年初的那段時間。
有句老話說“永遠也不知道明天和意外，哪一個會先來”，每每到了這樣的時候，心裏總是會生出一種不甘心，還有很多想去完成的事情，還有很
劉崇軍
2022-01-1022:41:24
GP不工作程序三維保護區的繪製
最近在利用居家隔離的時間，準備一些視頻課的素材，忽然就想起了GP不工作三維保護區的問題。
規範中提供的樣例不足以覆蓋實際工作中的方方面面，所以很多時候，只能基於規範的基本原理做一些延伸的分析，從三維演示的層面把問題探討清楚。
首先
劉崇軍
2022-01-1022:41:24
座標換算軟件操作方法及下載地址
昨天發文比較急，畢竟剛剛完成軟件的雞動心情還沒有平復，又趕着做視頻，所以有點語無倫次。
現在閱讀量總能上200多，相信能順利找到下載地址的朋友估計並不多。
有點佔用公共資源了，對不住熱心打開頁面閱讀的朋友。
今天剛好完成了用戶手冊的編寫，
劉崇軍
2022-01-1022:41:24
在高併發環境下該如何構建應用級緩存
摘要：立志成爲資深架構師的你，是否能夠在高併發環境下合理並且高效的構建應用級緩存呢？
本文分享自華爲雲社區《【高併發】在高併發環境下該如何構建應用級緩存？》，作者：冰河。
隨着我們的系統負載越來越高，系統的性能就會有所下降，此時，我們可以
華爲雲開發者社區
2021-12-2414:31:25
AI新手語音入門：認識詞錯率WER與字錯率CER
摘要：本文介紹了詞錯率WER和字錯率CER的概念，引入了編輯距離的概念與計算方法，從而推導得到詞錯率或字錯率的計算方法。
本文分享自華爲雲社區《新手語音入門(一)：認識詞錯率WER與字錯率CER｜編輯距離｜萊文斯坦距離｜動態規劃
華爲雲開發者社區
2021-12-2414:31:25
圖解帶你掌握`JVM`運行時核心內存區
摘要：堆空間差不多是最大的內存空間，也是運行時數據區最重要的內存空間。
堆可以處於物理上不連續的內存空間，但在邏輯上它應該被視爲連續的。
本文分享自華爲雲社區《醒酒菜：動畫圖解核心內存區--堆》，作者：阿Q說代碼。
堆的概述
一般來說：
華爲雲開發者社區
2021-12-2414:31:25
華爲超大雲數據中心落地貴州，這些硬核技術有利支撐“東數西算”
摘要：在貴州建設的數據中心又該如何最大化利用算力資源，從而有效提高資源分配率，降低雲資源的使用成本。
本文分享自華爲雲社區《華爲全球最大數據中心落地貴州，這些硬核技術有利支撐“東數西算”》，作者：技術火炬手。
貴州，位於我國西南地區，黃果樹
華爲雲開發者社區
2021-12-2414:31:25
TCP兩次握手爲什麼無法阻止歷史連接？
摘要：在兩次握手的情況下，「被動發起方」沒有中間狀態給「主動發起方」來阻止歷史連接，導致「被動發起方」可能建立一個歷史連接，造成資源浪費。
本文分享自華爲雲社區《TCP兩次握手爲什麼無法阻止歷史連接？》，作者：小林coding。
兩次握
華爲雲開發者社區
2021-12-2414:31:25
“數”馳天下，華爲雲DRS高效支撐T3出行平穩遷移
摘要：華爲雲DRS成功助力T3出行在規定時間內完成數十TB級全量數據的遷移。
數字化潮流浩浩湯湯，企業上雲如火如荼，網約車行業也藉助這一股東風展現出了蓬勃的生命力，因爲它的高效便捷，吸引了越來越多的都市人體驗。
T3出行是南京領行科技股份有
華爲雲開發者社區
2021-12-2414:31:25
一文帶你瞭解什麼是GitOps
摘要：說起GitOps，可能很多朋友馬上會聯想到DevOps，那麼GitOps和DevOps之間有什麼關係、又有什麼區別呢？
本文分享自華爲雲社區《淺談GitOps》，作者：敏捷的小智。
GitOps與DevOps
說起GitOps，可能
華爲雲開發者社區
2021-12-2414:31:25
Java學習筆記之報錯Exceptioninthread“main“java.io.FileNotFoundException
0x00概述
在JavaIO流章節進行練習的時候，運行代碼時候發現報錯，說文件路徑不正確。
0x01解決
報錯代碼
packageFileDemo2;
importjava.io.File;
importjava.io.
時光飛逝，逝者如斯
2021-12-2414:30:35
JaCoCo代碼覆蓋率從0到100的入門實踐
JaCoCo全稱是JavaCodeCoverage，Java代碼覆蓋率，廣泛運用於各種測試平臺對Java代碼的全量覆蓋率和增量覆蓋率進行統計，分析代碼行差異，度量單元測試效果。
Jacoco也是精準測試的技術實現手段之一。
入門實踐的目標
東方er
2021-12-2414:30:05
springboot項目提示Noconverterfoundforreturnvalueoftype:
延伸文章資訊
- 1「dfs應用」懶人包資訊整理(1)
103資訊學科培訓圖論圖論- BFS & DFS & 應用. 講者:林庭宇. 前情提要. 各位認識圖嗎? 基本概念. BFS & DFS 就是圖形的「搜索」; 實作時分別需要用到Queue & ...
- 2算法基礎：BFS和DFS的直觀解釋 - 每日頭條
本篇文章就單純來講講它們的區別和各自的應用，不會涉及任何代碼。我們以「圖的遍歷」為例，進行說明。 二、區別. 廣度優先搜索算法（Breadth-First- ...
- 3dfs與bfs的簡單總結及應用 - 台部落
dfs與bfs的簡單總結及應用 ... (1)：深度優先搜索（Depth-First-Search）是搜索算法的一種。是沿着樹的深度遍歷樹的節點，儘可能深的搜索樹的分支。當節點v ...
- 4圖的遍歷：DFS和BFS演算法- IT閱讀
以上是最基本的dfs演算法實現，事實上，程式碼結構絕不是一成不變的。 例如，應用dfs求一串元素的所有可能的排列，抽象出來的圖的分支就十分龐大。我們不 ...
- 5DAY11 - DFS應用 - iT 邦幫忙
DAY11 - DFS應用. 算法與數據結構&力扣例題實戰系列第11 篇. raychang0901. 4 個月前‧ 289 瀏覽. 0. 昨天寫了DFS模板，今天就搭配模板放幾題DFS的例題!!
