bfs能否解決一切dfs 問題？

12-31

指在時間複雜度相同的情況下，不考慮實現的難度和程序的運行效率。目前我還沒有想到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。時空能互換么？我覺得可以。