與其他算法相比，深度優先搜索是一個更好的解決方案，用於統計圖中連接組件的數量？

我找過方法來計算沒有。的在線連接組件。我注意到在大多數網站中，使用的算法是深度優先搜索。我相信你可以做到同樣的事情廣度優先搜索和聯盟找到。那麼爲什麼人們更喜歡使用DFS來查找連接組件的數量呢？與其他算法相比，深度優先搜索是一個更好的解決方案，用於統計圖中連接組件的數量？

來源

2017-10-08 Viktorja

我想你是在研究競爭性的編程資源。在那裏，簡單性贏了，DFS通常需要更少的代碼。在現實世界中，它可能不是最好的解決方案。 –

主要是因爲兩個原因：

它的簡單和短期。沒有數據結構是必需的（很好，我們需要一個堆棧，但遞歸處理）
它是內存友好型，Breath First Search的內存複雜度爲O(V)（V是節點數）。另一方面DFS有O(h)（h是遞歸樹的最大深度）。

來源

2017-10-08 11:27:32 Anonta

你是說沒有數據結構是必需的。但是，我看到了DFS的一個實現，其中有一個由頂點索引的布爾數組。該數組的目的是在遍歷過程中將每個頂點標記爲「visited」。因此，如果數組被稱爲「訪問」，並且如果訪問頂點5，則visited [5]被設置爲true。 – Viktorja

好吧，所以你暗示DFS只使用數組作爲數據結構，但其他算法使用更多的數據結構，這使得DFS更簡單。這是促成DFS更好的內存複雜性的原因之一嗎？ – Viktorja

是的。 DFS，當在節點'N'時，一次只在堆棧中存儲'N'個鄰居中的一個，而BFS將所有'N'個鄰居一次推入隊列中。 – Anonta

在複雜性方面它不會更好，因爲在所有情況下，您只需訪問一次節點。在內存使用方面，您將始終需要知道訪問了哪些節點以及哪些節點已找到並且尚未訪問。深度優先將在孩子的兄弟姐妹之前接受孩子節點並訪問其後代，而寬度優先將在孩子之前拜訪兄弟姐妹。深度優先是更短，更簡單，可以說是更直觀，這可能是其在教程，書籍和演示中比其他人更頻繁選擇的原因。

在很多情況下，要使用的堆棧是通過遞歸來處理的，但這不一定是個好主意，尤其是在大圖的情況下。

來源

2017-10-08 14:00:52

與其他算法相比，深度優先搜索是一個更好的解決方案，用於統計圖中連接組件的數量？

回答

相關問題