爲什麼選擇DFS而不是BFS查找圖中的循環

DFS主要用於在圖中找到一個循環而不是BFS。有什麼理由？兩者都可以在遍歷樹/圖時發現一個節點是否已經被訪問過。爲什麼選擇DFS而不是BFS查找圖中的循環

來源

2010-05-19 badcompany

您的圖表是否定向或不定向？ – 2010-05-19 22:16:42

在有向圖中，只有DFS可用於檢測週期;但是在無向圖中都可以使用。 – Hengameh 2015-08-16 05:33:46

深度優先搜索是更多的內存比廣度優先搜索有效，因爲你可以原路返回越快。如果使用調用堆棧，實現起來也更容易，但這依賴於最長的路徑而不是溢出堆棧。

此外，如果你的圖是directed那麼你必須不只是記住，如果你訪問了一個節點或沒有，還怎麼你到了那裏。否則，你可能會認爲你已經找到了一個循環，但實際上你所擁有的是兩條獨立的路徑A-> B，但這並不意味着有一條路徑B-> A。例如，

如果你BFS從0開始，它會檢測爲週期存在，但實際上沒有循環。

隨着所訪問，你下降和取消標記他們爲你原路返回，你可以標記一個節點深度優先搜索。查看有關此算法性能改進的評論。

對於best algorithm for detecting cycles in a directed graph你可以看看Tarjan's algorithm。

來源

2010-05-19 21:44:45

（記憶效率，因爲你可以回溯更早，也更容易實現，因爲你可以讓疊搭存儲開放清單，而不必明確地維護它的服務。） – Amber 2010-05-19 21:47:47

IMO，這只是如果你能依靠尾部更容易遞歸。 – 2010-05-19 21:48:58

+1用於指出雙路徑場景。 – 2010-05-19 21:57:33

DFS是更容易實現
一旦DFS發現一個週期，堆棧將包含形成周期的節點。 BFS也是如此，所以如果你想打印找到的循環，你需要做額外的工作。這使得DFS更加方便。

來源

2010-05-19 21:51:24 IVlad

如果你把一個循環的一種樹隨機點，DFS往往會擊中時，它覆蓋在樹上一半的週期，一半的時間就已經走過這裏循環下去，一半（它會平均在樹的其餘部分中找到它的一半），所以它將平均評估樹的約0.5 * 0.5 + 0.5 * 0.75 = 0.625。

如果你在一棵樹的隨機點放置一個週期，BFS將趨向於打循環，只有當它的評估樹的層在那個深度。因此，通常最終必須評估平衡二叉樹的葉子，這通常會導致評估更多的樹。特別是，3/4的時間至少有兩條鏈接中的一條出現在樹的樹葉中，在這些情況下，您必須平均評估樹的3/4（如果有一個鏈接）或7/8的樹（如果有兩個），所以你已經達到了搜索1/2 * 3/4 + 1/4 * 7/8 =（7 + 12）/ 32 = 21/32 = 0.656 ...的樹，甚至沒有增加搜索帶有從葉節點附加的週期的樹的成本。

另外，DFS比BFS更容易實現。因此，除非您知道關於您的週期的一些事情（例如週期可能接近您搜索的根源，此時BFS爲您提供優勢），否則這是一個使用。如果是無向圖（是我做客表示使用BFS，將在一個有向圖報告週期的高效算法！），其中每個「橫邊緣」限定了循環

來源

2010-05-19 21:53:05

那裏有很多神奇的數字。我不同意「DFS更快」的論點。這完全取決於輸入，在這種情況下沒有輸入比另一個輸入更普遍。 – IVlad 2010-05-19 21:56:51

@Vlad - 這些數字並不神奇。它們是手段，都是這樣表述的，並且根據我所陳述的假設，計算幾乎是微不足道的。如果用均值近似是一個不好的近似值，那將是一個有效的批評。（我明確指出，如果你可以對結構做出假設，答案可能會改變。） – 2010-05-20 03:10:56

這些數字是神奇的，因爲它們不代表什麼。您將DFS做得更好，並將這些結果推測爲一般情況。你的陳述是沒有根據的：「當DFS覆蓋大約一半的樹時，DFS將趨向於這個週期」：證明它。更不用說你不能在樹上談論循環。根據定義，樹沒有循環。我只是不明白你的意思。 DFS將會以一種方式運行，直到它陷入死衚衕，所以你無法知道它平均將探索多少GRAPH（不是樹）。你只是選擇了一個沒有任何證據的隨機案例。 – IVlad 2010-05-20 07:35:34

甲BFS可能是合理的。如果交叉邊沿爲{v1, v2}，並且包含這些節點的根（在BFS樹中）爲r，則週期爲r ~ v1 - v2 ~ r（~是一條路徑，單邊沿爲-），其報告幾乎與DFS中一樣容易報告。

使用BFS的唯一原因是如果你知道你的（無向）圖將有長路徑和小路徑覆蓋（換句話說，深和窄）。在這種情況下，BFS將比DFS的堆棧（當然仍然是線性的）要求其隊列內存的比例更少。

在所有其他情況下，DFS顯然是贏家。它既適用於有向圖也適用於無向圖，並且報告循環很簡單 - 只需將任何後端連接到從祖先到後代的路徑，即可獲得循環。總而言之，這個問題比BFS更好，更實用。

來源

2010-05-20 08:53:01

BFS不會工作在尋找週期有向圖。考慮A-> B和A-> C-> B作爲圖中A到B的路徑。 BFS會在沿B路訪問的路徑之一後說。當繼續前進下一個路徑時，它會說已標記的節點B已被再次找到，因此，有一個循環。顯然這裏沒有周期。

來源

2015-01-29 06:00:38

您能否解釋DFS如何明確識別您的示例中不存在的循環？我同意循環在所提供的示例中不存在。但是如果我們從A-> B然後A-> C-> B，我們將發現B已經被訪問，其父母是A不是C..and我讀DFS將通過比較已經訪問過的元素的父節點與當前節點從我們在這個時候檢查的方向來檢測週期.am我得到DFS錯誤或者是什麼？ – smasher 2017-10-20 14:44:44

您在這裏展示的所有內容都是這個特定的實現不起作用，而不是BFS所不可能的。事實上，它*是可能的，儘管它需要更多的工作和空間。 – Prune 2017-11-17 17:45:00

@Prune：所有線程（我認爲）在這裏試圖證明bfs不會用於檢測週期。如果你知道如何反證，你應該提供證據。簡單地說，努力是更大的將不會滿足 – 2017-11-19 06:47:25

證明一個圖是循環的，你只需要證明它有一個週期（邊緣往自身直接或間接指向）。

在DFS，我們需要一個頂點的時間和檢查是否有循環。只要找到一個循環，我們可以省略檢查其他頂點。

在BFS中，我們需要同時跟蹤許多頂點邊緣，並且在最後找出是否有周期。隨着圖形大小的增加，與DFS相比，BFS需要更多的空間，計算和時間。

來源

2015-07-28 01:32:24 Spiker

，如果你談論的是遞歸或迭代實現類的依賴。

遞歸的DFS訪問每個節點兩次。迭代-BFS訪問每個節點一次。

如果要檢測循環，則需要在添加鄰接點之前和之後調查節點 - 無論是在節點上「啓動」還是在「完成」節點時。

這需要更多的迭代BFS工作，所以大多數人選擇遞歸-DFS。

請注意，迭代-DFS與std :: stack的簡單實現具有與迭代-BFS相同的問題。在這種情況下，您需要將虛擬元素放入堆棧以跟蹤何時「完成」在節點上工作。

看到這個答案，詳細瞭解迭代的DFS如何需要額外的工作，以確定何時「完成」與一個節點（在TopoSort的情況下回答）：

Topological sort using DFS without recursion

希望這解釋了爲什麼人們喜歡遞歸-DFS來處理需要確定何時「完成」處理節點的問題。

來源

2016-02-09 20:28:46

爲什麼選擇DFS而不是BFS查找圖中的循環

回答

相關問題