優先深度優先搜索廣度優先搜索或反之亦然

我研究了兩種圖遍歷算法，深度優先搜索和廣度優先搜索。由於兩種算法都用於解決圖遍歷的相同問題，所以我想知道如何在兩者之間進行選擇。我的意思是比另一個更有效率，或者說爲什麼我會在特定場景中選擇另一個。優先深度優先搜索廣度優先搜索或反之亦然

謝謝你

2012-05-15 Kris

請參閱http://stackoverflow.com/questions/687731/breadth-first-vs-depth-first ...包含一些有用的信息和鏈接，包括鏈接到最後兩個答案之一的3部分博客。 – hatchet

感謝分享this.It看起來真的很有用。實際上，我明白這兩種算法如何工作，只是想知道爲什麼我們需要其中兩個:) – Kris

類似於http://stackoverflow.com/questions/1657174/what-對於 – hatchet

與我的主要區別是有些理論上的。如果你有一個無限大小的圖，那麼如果它存在於它選擇的第一個路徑之外，DFS將永遠不會找到一個元素。它基本上會繼續沿着第一條路走下去，永遠不會找到這個元素。 BFS最終會找到這個元素。

如果圖的大小是有限的，那麼DFS可能會更快地發現異常值（根與目標之間的距離更大），因爲BFS會更快地找到更近的元素。除了DFS選擇淺層元素的路徑。

來源

2012-05-15 17:50:37 Justin

這不是一個錯誤的答案，但是DFS和BFS都可以在無限的情況下失敗 - 如果圖形無限深，DFS可能會失敗，而BFS可以工作。但是，如果圖形不是無限深的，而是無限*廣泛*，則DFS將起作用，而BFS將失敗。遍歷無限圖（根據我的理解）與遍歷有限圖大不相同。 –

一般來說，BFS對於找到最短路徑或相關問題相關的問題更好。因爲在這裏你從一個節點到所有與它相鄰的節點，因此你有效地從路徑長度移動到路徑長度二，等等。

雖然另一端的DFS更有助於解決連接問題，並且還可以查找圖表中的循環（儘管我認爲您也許可以通過修改BFS來查找循環）。確定與DFS的連接性是微不足道的，如果您從DFS過程中調用兩次瀏覽過程，那麼圖形將斷開連接（這是針對無向圖的）。這裏可以看到有向圖的強連通分量算法，這是對DFS的修改。 DFS的另一個應用是拓撲排序。

這些都是算法的一些應用：

DFS：

連接
強連通分量
拓撲排序

BFS：

最短路徑（Dijkstra算法是一些什麼的BFS修改）。
測試圖形是否爲二分圖。

來源

2012-05-15 18:14:33 sukunrt

對於完整/完美的樹，DFS相對於樹的深度需要線性空間量，而BFS相對於樹的深度需要指數量的空間。這是因爲對於BFS，隊列中的最大節點數與樹的一個級別中的節點數成比例。在DFS中，堆棧中的最大節點數量與樹的深度成比例。

來源

2015-01-01 00:28:41

當遍歷多連接圖時，遍歷節點的順序可能會對遍歷方法要跟蹤的節點數量產生很大影響（以多個數量級）。某些種類的算法在使用寬度優先時會大大提高;其他人在使用深度搜索時會大大改善。

一方面，對具有N個葉節點的二叉樹進行深度優先搜索要求遍歷方法跟蹤lgN節點，而廣度優先搜索需要跟蹤至少N/2個節點（因爲它在掃描任何葉節點之前可能會掃描所有其他節點;在掃描第一個葉節點之前，它將遇到葉節點的父節點的N/2個，這些節點必須單獨進行跟蹤，因爲它們都沒有相互引用）。另一個極端是，用一種方法在NxN網格上進行填充，如果其像素尚未着色，則對該像素進行着色，然後對其鄰居進行洪水填充將需要排入O（N）如果使用寬度優先搜索，則使用像素座標;如果使用深度優先，則使用O（N^2）像素座標。在使用廣度優先搜索時，無論要繪製的形狀如何，繪畫都會「展開」當使用深度優先算法繪製矩形螺旋時，每條直線的一側是直的而另一側是交錯的（哪一側應該是直的並且鋸齒取決於所使用的確切算法），所有的直線部分將被繪製在任何鋸齒狀之前，意味着系統必須分別跟蹤每個鋸齒的位置。

來源

2015-04-30 17:01:20 supercat

在某些語言中，BFS是一個稍微更好的選擇因爲最簡單的實現DFS的是遞歸的，它引入了額外的開銷，而且也可能會導致您的代碼打堆棧大小限制大圖。 BFS的明顯優勢（和應用）是，在未加權圖中它可以用來構造從u到v的最短路徑。這有很多應用程序 - 例如，您可以計算最少的移動次數需要通過在其狀態空間上運行BFS來解決給定的難題。 BFS甚至可以爲您提供一個頂點u到圖中所有其他頂點的最短距離：對於每個頂點，只需記住用於發現它的邊緣。

來源

2015-10-28 02:53:12

優先深度優先搜索廣度優先搜索或反之亦然

回答

相關問題