【算法基礎(chǔ)】回溯算法和DFS(深度優(yōu)先搜索)到底有什么區(qū)別？

DFS 英文名，Depth First Search，中文名?深度優(yōu)先搜索，是圖的一種搜索算法，每一個可能的分支路徑深入到不能再深入為止，且每個節(jié)點只能訪問一次。

深度優(yōu)先搜索算法跟圖結(jié)構(gòu)緊密相關(guān)，任何涉及深度度優(yōu)先搜索的問題，都伴隨著圖。

深度度優(yōu)先搜索的能夠在圖結(jié)構(gòu)里搜索到通往特定終點的一條或者多條特定路徑。

回溯算法是系統(tǒng)地搜索問題的解的方法。

某個問題的所有可能解的稱為問題的解空間，若解空間是有限的，則可將解空間映射成樹結(jié)構(gòu)。

任何解空間可以映射成樹結(jié)構(gòu)的問題，都可以使用回溯法。

回溯法是能夠在樹結(jié)構(gòu)里搜索到通往特定終點的一條或者多條特定路徑。

回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試，從而搜索到抵達(dá)特定終點的一條或者多條特定路徑。

值得注意，回溯法以深度優(yōu)先搜索的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。

因此，回溯算法 = 深度優(yōu)先搜索 + 剪枝函數(shù) 這一說法并沒有錯。但這一結(jié)論也并不十分正確。

誠然，如上面所言，深度優(yōu)先搜索是特定于圖結(jié)構(gòu)的一種搜索算法，回溯算法是特定于樹結(jié)構(gòu)的搜索算法。

那為何?回溯算法 = 深度優(yōu)先搜索 + 剪枝函數(shù)這一說法沒有錯？

因為樹是特殊的圖。簡單來說，樹是廣義的圖。再簡單來說，樹是圖。

因此，回溯算法與深度優(yōu)先搜索的關(guān)系也昭然若揭。因為，實施算法的對象（數(shù)據(jù)結(jié)構(gòu)）都是圖，所以，兩者可以相提并論，存在一些共性，回溯算法也得以在搜索時使用深度優(yōu)先算法。

也顯而易見，回溯算法 也并不簡單的可以說回溯算法 = 深度優(yōu)先搜索 + 剪枝函數(shù)。

因為并不是所有圖都是樹。

深度優(yōu)先搜索適用于所有圖。而回溯算法只適用于樹結(jié)構(gòu)。

任何解空間可以映射成樹結(jié)構(gòu)的問題，都可以使用回溯法。任何解空間不能映射成樹結(jié)構(gòu)的問題，都不可以使用回溯法。

說到這里，大概也弄明白了兩者的關(guān)系。

陳述一個比較正確的結(jié)論：

回溯算法 = 樹的深度優(yōu)先搜索 + 剪枝函數(shù)

還需要強(qiáng)調(diào)的是，遞歸不遞歸跟算法毫無關(guān)系，遞歸只是算法的實現(xiàn)方式、算法代碼化的手段。

另外注意，任何遞歸形式的算法都能通過棧、隊列等數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)化為非遞歸的形式。

最后再說一句，思想不思想、方式不方式、具體不具體、狀態(tài)不狀態(tài)跟算法也毫無關(guān)系。

算法說思想、方式、具體、狀態(tài)，人說格局、態(tài)度。

很高大上，但沒啥用，沒任何內(nèi)涵跟意義。

一切解決特定問題的步驟的描述統(tǒng)稱為算法。

回溯算法 跟 深度優(yōu)先搜索算法都很經(jīng)典，同為經(jīng)典算法必須掌握。它們的區(qū)別跟關(guān)聯(lián)都在于它們的數(shù)據(jù)結(jié)構(gòu)，回溯算法是樹結(jié)構(gòu)，深度優(yōu)先搜索是圖結(jié)構(gòu)。樹與圖的相似點跟不同點導(dǎo)致了回溯算法跟深度優(yōu)先搜索算法的存在相似點、也存在不同點。

參考資料：

[1] 回溯算法和DFS(深度優(yōu)先搜索)到底有什么區(qū)別？