BFS和DFS的用途是什麼？

Question

我已經瞭解了這些算法是如何工作的，但是它們用於什麼？

難道我們用它們來：

• 找到一個圖中的某個節點或
• 找到最短路徑或
• 找到一個週期的圖形

？

他們都只是訪問所有的節點，並標記他們訪問過，我不明白這一點。

我有點迷失在這裏，我正在學習。

Answer 1

BFS和DFS是圖形搜索算法，可用於各種不同的目的。

這兩種搜索技術的一個常見應用是識別從給定起始節點可到達的所有節點。例如，假設您有一組計算機，每臺計算機都連接到少數其他計算機。通過從給定節點運行BFS或DFS，您將發現網絡中原始計算機可以直接或間接與之通話的所有其他計算機。這些是標記回來的電腦。

BFS專門用於查找未加權圖中兩個節點之間的最短路徑。例如，假設您想要將數據包從網絡中的一臺計算機發送到另一臺計算機，並且計算機之間沒有直接連接。應該沿着什麼路線發送數據包，使其儘快到達目的地？如果你運行一個BFS，並且在每次迭代時每個節點都存儲一個指向其「父」節點的指針，那麼你最終將找到從開始節點到圖中每個其他節點的路由，從而最小化必須遍歷的鏈路的數量到達目標計算機。

DFS通常用作更復雜算法的子程序。例如，Tarjan用於計算強連接組件的算法基於深度優先搜索。許多優化的編譯器技術通過適當構建的圖形運行DFS，以確定應用特定系列操作的順序。深度優先搜索也可用於迷宮生成：通過獲取節點網格並將每個節點鏈接到它的鄰居，您可以構建代表網格的圖形。在該圖上運行隨機深度優先搜索，然後生成一個只有一個解決方案的迷宮。

這絕不是一個詳盡的列表。這些算法具有各種各樣的應用程序，當您開始探索更高級的算法時，您經常會發現自己依賴DFS和BFS作爲構建塊。它與排序相似 - 排序本身並不是那麼有趣，但能夠排序值列表作爲更復雜算法中的子程序非常有用。

希望這會有所幫助！