廣度優先搜尋與深度優先搜尋的差異：造訪順序、實作方式、最短路徑、記憶體與用途比較
兩者都是沿著邊，不遺漏地造訪圖或樹之頂點的搜尋方法。廣度優先搜尋（BFS）先造訪從起點走1條邊可到達的所有頂點，再到走2條邊可到達的頂點，依由近到遠的順序擴展。深度優先搜尋（DFS）沿著一條路盡可能地往前走，走到盡頭時就退回，改走另一條路。廣度優先搜尋以佇列實作，深度優先搜尋以堆疊或遞迴實作；若以鄰接串列表示圖，兩者都以與頂點數加邊數成正比的工夫造訪全部頂點。求無權重之圖的最短路徑時多用廣度優先搜尋，要窮舉所有路徑或偵測環路時多用深度優先搜尋。
| 項目 | 廣度優先搜尋（BFS） | 深度優先搜尋（DFS） |
|---|---|---|
| 造訪的順序 | 依離起點由近到遠（經過的邊數由少到多）的順序，一層一層擴展 | 沿一條路走到底，走到盡頭就退回，再走下一條路 |
| 使用的資料結構 | 佇列（先進先出） | 堆疊（後進先出），或遞迴呼叫 |
| 最短路徑 | 在邊沒有權重的圖中，第一次到達時經過的邊數，就是離起點的最短距離 | 不保證最短。可能經由繞遠路的路徑先到達 |
| 時間複雜度（頂點數V、邊數E） | 鄰接串列為O(V + E)，鄰接矩陣為O(V²) | 與廣度優先搜尋相同，鄰接串列為O(V + E)，鄰接矩陣為O(V²) |
| 使用的記憶體 | 把接下來要造訪的頂點記在佇列中。分支多時，一整層的頂點會一起放進佇列，佇列會變大 | 以遞迴撰寫時，只需記住目前路徑上的頂點，與路徑的深度成正比。太深時，呼叫堆疊可能溢位 |
| 能否找到解 | 頂點有限時一定找得到。即使搜尋範圍無限擴展，也會從較淺位置的解依序找到 | 在有限的圖中記錄已造訪的頂點，就一定找得到。路徑可能無限加深時，可能沿一條路一直走下去而不回頭 |
| 走訪樹的順序 | 層序（從根開始逐層，由左到右） | 前序、中序、後序 |
| 主要用途 | 無權重之圖的最短路徑、迷宮的最少步數、計算網路能到達幾跳之外 | 迷宮或謎題的全部情形搜尋（回溯法）、偵測連通分量與環路、拓撲排序 |
數值為具代表性的大致參考值，會因世代或產品而異。