2019獨角獸企業重金招聘Python工程師標準>>>

深度優先搜索

深度優先搜索是對圖的一種遍歷方式，如命所示，只要有可能，就盡可能的“深入”。以下為《算法導論》中對深度優先搜索的解釋：

深度優先搜索總是對最近才發現的結點 v 的出發邊進行探索，直到該結點的所有出發邊都被發現為止。一旦結點 v 的所有出發邊都被發現，搜索則“回溯”到 v 的前驅結點（v 是經過該結點才被發現的），來搜索該前驅結點的出發邊。
該過程一直持續到從源結點可以達到的所有結點都被發現為止。如果還存在尚未發現的結點，則深度優先搜索將從這些未被發現的結點中任選一個作為新的源結點，并重復同樣的搜索過程。該算法重復整個過程，直到圖中的所有結點都被發現。

深度優先搜索的實現

實現深度優先搜索，通常使用遞歸的方式，也可以是利用棧來實現。
而深度優先搜索可以分為先序，中序，后序，也就是我們所熟悉的樹的遍歷的方式。這三種方式本質上還是遵循于深度優先搜索的原則，即盡可能的“深入”，不同的是對結點的處理時機，如先序遍歷總是先對當前結點進行了處理，再繼續遍歷，而后序遍歷則是遍歷到葉子結點才逐步對結點進行處理。
關于樹的遍歷的知識可以參考 Construct Binary Tree From Preorder and Inorder Traversal Solution 文章中 How to traverse the tree 一節。

以下為參考自《算法導論》的深度優先搜索的偽代碼：

# 用于記錄時間 time = 0def dfs_visit(graph, u):time = time + 1# 被發現的結點標記為灰色，d 為結點的發現時間u.color = GRAYu.d = timefor v in graph.Adj[u]:if v.color == WHITE:v.p = udfs_visit(graph, v)# 完成處理的結點標記為黑色，f 為結點的結束時間u.color = BLACKtime = time + 1u.f = timedef dfs(graph):# 圖的初始化for vertex in graph.V:vertex.color = WHITE# p 為結點的前驅屬性vertex.p = Nonefor vertex in graph.V:if vertex.color == WHITE:dfs_visit(graph, vertex)

需要注意的是，我們是對圖進行深度優先搜索，在初學深度優先搜索的時候，總是會將問題局限為對樹的搜索，樹是圖的一種，局限思維往往會導致無法解決問題。

深度

深度優先搜索可以將結點按層劃分，也就是遍歷的深度，每進行一次遞歸，就是對下一層結點的訪問。
在搜索時記錄深度，可以在搜索時確認當前遍歷到的結點的一些具體信息。

有以下例題：Find Largest Value in Each Tree Row
該題目就是找出樹的每一層的最大值。在遍歷時記錄了深度，然后讓同層結點進行比較即可。以下為解題源碼：

# Definition for a binary tree node. class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def largestValues(self, root):""":type root: TreeNode:rtype: List[int]"""MIN_VALUE = -2**31def dfs(node, depth, res):if depth not in res:res[depth] = MIN_VALUEres[depth] = max(res[depth], node.val)if node.left is not None:dfs(node.left, depth + 1, res)if node.right is not None:dfs(node.right, depth + 1, res)if root is None:return []res = dict()dfs(root, 0, res)return list(res.values())

再看以下例題：Binary Tree Right Side View

這條題目的要求就是找出樹每一層的最右結點。同樣這需要在遍歷時記錄深度，而且需要我們能夠有逆向思維。
通常對樹的深度優先搜索都是采取于先序遍歷的方式，也就是在遍歷時優先訪問左子結點。在這種情況下，樹每一層的最右結點可以看作為該層的最后一個結點。
但是這樣的問題在于，在遞歸的情況下，“最后一個”是難以知悉的，當然深度優先搜索可以利用棧去完成，用棧的話可以控制到“最后一個”。
這里就需要逆向的思維，在深度優先搜索中優先訪問左子結點，那么每次遞歸時每一層最先發現的結點即為的最左結點，這時我們反過來，優先訪問右子節點即可。
以下為解題源碼：

# Definition for a binary tree node. class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def rightSideView(self, root):""":type root: TreeNode:rtype: List[int]"""def dfs(node, depth, res):if depth not in res:res[depth] = node.valif node.right is not None:dfs(node.right, depth + 1, res)if node.left is not None:dfs(node.left, depth + 1, res)if root is None:return []res = {}dfs(root, 0, res)return list(res.values())

在深度優先搜索中，對深度信息的掌握其實就是對遍歷中所在結點的“位置”的掌握，而有時候就需要圍繞這個“位置”的信息來進行解決問題。

轉載于:https://my.oschina.net/bingzhong/blog/3005037

總結

以上是生活随笔為你收集整理的深度优先搜索知识总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。