bfs能否解決一切dfs 問題?

指在時間複雜度相同的情況下,不考慮實現的難度和程序的運行效率。目前我還沒有想到dfs能做而bfs不能做的事情

例如求dfs序的問題大概求一個子樹的size給每個兒子分配dfs區間就好了

tarjan的幾個問題(強聯通、雙聯通、支配樹等)只要先用BFS隨便搞出一顆DFS樹,在DFS樹上按順序求得答案就好了吧。


你要這麼想:顯然如果你能遍歷整個解空間,那怎麼搜都無所謂。但如果你不能呢?例如,什麼時候bfs能做但dfs不能做呢?當深度無限的時候。同理,如果寬度無限但深度有限,那bfs就掛了,dfs反而可以。

例如,求兩個整數,使得它們的和為0。


前提是節點有限

另外時間複雜度相同的情況是指什麼啊,時間複雜度是要演算法先存在才能去評估,而你這裡是問對於某個有dfs方法的問題是否存在bfs方法


不能。

存在子節點數量無上限(數學或工程層面的)的問題。

舉個實際的巡路問題的例子:

在非grid化的場景下進行巡路,單步距離固定為r。

對於b對於bfs,子節點集合是以父節點為圓心的圓,可無限劃分。

對於dfs,可任選一子節點巡路,如失敗可以二分方式逼近最終達到目標。


雙連通分量、強連通分量、拓撲排序這種用到dfs樹性質的bfs當然就不行了……dfs相對bfs的好在於它得到的樹性質非常好,在無向圖的時候沒有橫向邊,便於做各種事情……


如果你已經約束了時間複雜度相同,我想樹的構型參數也是確定的,你的推論可以成立。

實際工程中很少遇到這種情形


如果只是遍歷,你做布朗運動直到遍歷完都沒問題,和DFS也是一樣的。

但是DFS還有一個重要的價值就是它的訪問樹,這棵樹的很多性質可以用來解決問題的,我就說一個例子,強連通分量,題主可以自己去搜,這個演算法實在是牛逼閃閃。

所以說年輕人問這種naive的問題之前還是先多讀演算法導論啊


iddfs=省空間版bfs

判斷無解?如果當前搜索沒有因為到達最大深度而返回的話,則無解。

(用常數換空間)

dfs寫回溯比bfs方便。


https://github.com/thautwarm/cache/blob/master/forfun/FS.py

bfs也可以有深度這個概念啊。波浪是一圈圈的。

至於寬度無限...

其實可以學一下如何遍歷 N 	imes N 的構造,從起點開始,依次走深寬度為1,2,3,4,5, ...


想了一下,在滿足不知道解答樹上的點的後繼是否有解(不能剪枝)(也就是無法估價)的前提下,只有解答樹收束(多解)的模型才會出現dfs比bfs優的情況。QAQ。所以也許不能剪枝的單解問題中bfs一定比dfs優?Orz 其他答案中提到的寬度無限的情況......我覺得單解問題中某層解答不能被估價,那就隨機進入下一層的某個點咯。而這層點又是無窮多,那這樣的話進入正解所在的解答子樹的概率不就趨於0了嗎……所以我覺得dfs要麼能剪枝,要麼就打打多解(比如高票說的輸出兩個和等於0的數),其他情況下bfs一定比dfs優。


dfs可以從很深的地方回溯,而bfs不行。

舉個例子。

給定一個無限長的白氣球序列,以及n個操作,每個操作包含兩個顏色,表示在所有a顏色的氣球後面插入一個b顏色的氣球。最後問整個氣球序列的前m個氣球分別是什麼顏色。n,m=200000

dfs可以O(n+m)解決,bfs很難做到。


深度有限 寬度無限的情況,bfs就gg了


找字典序最小


時間無限dfs,空間無限bfs。時空能互換么?我覺得可以。


推薦閱讀:

自編一道動規題,可以從哪幾個方面增加難度?
如何看待信息學競賽中的學校殺制度?
成為一個OIer/當過一個OIer是一種怎樣的體驗?
n個有重複數,求其一種排列使得前綴和絕對值的最大值最小,有較好的演算法嗎?
為什麼 Dev C++ 特別流行?

TAG:演算法 | 編程 | OI | ACM競賽 |