【原】Python|DFS（深度優(yōu)先搜索）介紹

算法與編程之美 2020-08-08

展開全文

問題描述

在眾多算法中，時常會用到一種適用于大多數情況的方法，這就是遍歷。遍歷中的DFS（深度優(yōu)先搜索）就是今天要介紹的。DFS有遞歸性結構中最重要的一些屬性，一旦在某個節(jié)點啟動了DFS，就能確保自己能在相關操作繼續(xù)下去之前遍歷完其他所有能達到的節(jié)點。

解決方案

任何遞歸函數都可以用迭代操作來寫，一種做法是用棧來模擬調用棧。這種基于迭代操作的DFS是非常實用的，它既可以避免調用棧被塞滿帶來的問題，也能因此改善算法的某些屬性，使其顯得更為清晰一些。為了模擬遞歸遍歷，只需要使用一個棧結構。

代碼示例(迭代DFS) ：

def iter_dfs(G,s):
    S,Q = set(),[]   #訪問集合和隊列
    Q.append(s)      #我們計劃訪問s
    while Q:
        u = Q.pop() #使程序進展
        if u in S:continue #是否訪問過？跳過
        S.add(u)
        Q.extend(G(u))
        yield u             #u就是我們要的

為了讓這段遍歷更實用，添加了一個yield語句，它能按照DFS的順序來遍歷目標結構中的節(jié)點。DFS按照“先序遍歷的方式”對頂點進行訪問，其核心是棧的使用，而且可以用遞歸實現。

END

實習主編 | 王楠嵐

責編 | 劉仕豪

where2go 團隊

微信號：算法與編程之美