🎈 作者：Linux猿
🎈 簡介：CSDN博客專家🏆，C/C++、面試、刷題、演算法盡管咨詢我，關注我，有問題私聊！
🎈 關注專欄：C/C++面試通關集錦 （優質好文持續更新中……）🚀
目錄
一、什么是 bfs ?
1.1 搜索方式
二、什么是 dfs ?
2.1 搜索方式
三、bfs 和 dfs 的區別
3.1 資料結構
3.2 訪問節點的方式
3.3 應用
大家對 bfs 和 dfs 應該都有了解，都是很常用的搜索演算法，本文結合實體來講解下這兩者的不同，
一、什么是 bfs ?
bfs 是 Breadth-First Search 的縮寫，稱為廣度優先搜索，或寬度優先搜索，
1.1 搜索方式
步驟 1：從源點出發，訪問源點的鄰居結點，將鄰居節點依次放入佇列中，并標記為已訪問；
步驟 2：取出佇列中的鄰居結點，依次訪問每個節點未被訪問的鄰居節點；
步驟 3：將鄰居節點依次放入佇列中，并標記為已訪問；
步驟 4：重復步驟 2~3 直到訪問到目標節點或所有節點都標記為已訪問，
來看一個簡單的例子，下面是一個無向圖：
使用廣度優先搜索遍歷上圖，節點的訪問順序是（假設相同鄰居節點優先訪問編號小的節點）：
1 -> 2 -> 3 -> 5 -> 4 -> 6 -> 7
二、什么是 dfs ?
dfs 是 Depth-First-Search 的縮寫，稱為深度優先搜索，
2.1 搜索方式
步驟 1：從源點出發，訪問源點的某個鄰居節點，將其放入堆疊中，并標記為已訪問；
步驟 2：從堆疊中取出一個節點，訪問該節點的未被訪問的鄰居節點；
步驟 3：將鄰居節點放入堆疊中，并標記為已訪問；
步驟 4：重復步驟 2 ~ 3，直到訪問到目標節點或所有節點都標記為已訪問；
來看一個簡單的例子，下面是一個無向圖：
使用深度優先搜索遍歷上圖，節點的訪問順序是（假設相同鄰居結點先訪問編號小的節點）：
1->2->4（4 節點沒有未訪問的鄰居結點回傳到 2 節點）-> 5 -> 6->3->7
一般來說，bfs 和 dfs 在不同的場景下都有效，但是，采用的演算法不同，程式執行的效果會有差異，應該選擇合適的演算法，
三、bfs 和 dfs 的區別
3.1 資料結構
bfs 遍歷節點是先進先出，一般使用佇列作為輔助資料結構，dfs遍歷節點是先進后出，一般使用堆疊作為輔助資料結構；
3.2 訪問節點的方式
bfs是按層次訪問的，先訪問源點，再訪問它的所有相鄰節點，并且標記結點已訪問，根據每個鄰居結點的訪問順序，依次訪問它們的鄰居結點，并且標記節點已訪問，重復這個程序，一直訪問到目標節點或無未訪問的節點為止，
dfs 是按照一個路徑一直訪問到底，當前節點沒有未訪問的鄰居節點時，然后回溯到上一個節點，不斷的嘗試，直到訪問到目標節點或所有節點都已訪問，
3.3 應用
bfs 適用于求源點與目標節點距離近的情況，例如：求最短路徑，dfs 更適合于求解一個任意符合方案中的一個或者遍歷所有情況，例如：全排列、拓撲排序、求到達某一點的任意一條路徑，
🎈 歡迎小伙伴們點贊👍、收藏?、留言💬
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/291205.html
標籤：其他