DFS學習歸納總結

2019-11-06 06:18:47

字體：大中小

來源：轉載

供稿：網友

看了幾次題，dfs還是用的比較多的一種算法，上次做阿里的編程題也是深搜加剪枝。太久沒寫了，大學學的一點皮毛也都荒廢了。

DFS

這篇博客寫的很好，偽代碼也清晰明了：深度優先搜索(DFS) 算法入門

c++代碼

/** * DFS核心偽代碼 * 前置條件是visit數組全部設置成false * @param n 當前開始搜索的節點 * @param d 當前到達的深度，也即是路徑長度 * @return 是否有解 */ bool DFS(Node n, int d){ if (d == 4){//路徑長度為返回true，表示此次搜索有解 return true; } for (Node nextNode in n){//遍歷跟節點n相鄰的節點nextNode， if (!visit[nextNode]){//未訪問過的節點才能繼續搜索 //例如搜索到V1了，那么V1要設置成已訪問 visit[nextNode] = true; //接下來要從V1開始繼續訪問了，路徑長度當然要加 if (DFS(nextNode, d+1)){//如果搜索出有解 //例如到了V6，找到解了，你必須一層一層遞歸的告訴上層已經找到解 return true; } //重新設置成未訪問，因為它有可能出現在下一次搜索的別的路徑中 visit[nextNode] = false; } //到這里，發現本次搜索還沒找到解，那就要從當前節點的下一個節點開始搜索。 } return false;//本次搜索無解 }

算法中要注意：要有出口（搜索到滿足條件的時候返回）；利用visit數組標記，訪問一個點就將其先標記再訪問；當前遞歸返回時，如果沒有返回true，要將之前標記過得點重置。

關于搜索剪枝算法之后再補充。

上一篇：Application傳值

下一篇：disney (map模擬)