Python 中的深度優先搜尋
深度優先搜尋是一種遍歷樹或圖的演算法。在 DFS 中，遍歷從根節點開始，越走越深。
當它到達葉節點時，它會執行回溯並向上。
深度優先搜尋用於許多應用程式，例如：
- 檢測圖中的迴圈
Path Finding旅行推銷員問題
在 Python 中使用 Graph 的深度優先搜尋示例
我們有六個頂點，1 是根頂點。我們將遍歷 1，然後它有兩個相鄰的頂點 5 和 9，所以首先我們將遍歷它的左頂點，然後我們將遍歷 5 的相鄰頂點。
當找到葉節點時，我們將回溯並重復相同的過程到最近未訪問的節點。
在這個例子中，綠色頂點是遍歷的頂點，而紅色是尚未遍歷的頂點。
在 Python 中使用遞迴進行深度優先搜尋
recursion 技術呼叫 DFS 函式。遍歷所有圖的頂點時，基本條件為真。
以下程式碼使用字典資料結構來表示鄰接列表以將圖形儲存在記憶體中。
我們將宣告一個集合來跟蹤我們訪問過的所有頂點。
如果頂點沒有被遍歷，我們首先通過列印它並將其新增到遍歷集中來遍歷它。
# Python 3.x
graph = {
'1' : ['5','9'],
'5' : ['2', '4'],
'9' : ['8'],
'2' : ['4'],
'4' : ['2'],
'8' : []
}
traversed = set()
def dfs(traversed, graph, vertex):
if vertex not in traversed:
print (vertex)
traversed.add(vertex)
for adjacent in graph[vertex]:
dfs(traversed, graph, adjacent)
print("Depth First Search:")
dfs(traversed, graph, '1')
輸出：
# python 3.x
Depth First Search:
1
5
2
4
9
8
我們必須通過遍歷圖的相鄰頂點並執行 DFS 來越來越深入。
我們回溯，訪問了最近未訪問的頂點，併為該頂點執行了 DFS。
在驅動程式程式碼中，我們必須呼叫 dfs 函式並指定根頂點，在我們的例子中是 1。
在 Python 中使用迭代進行深度優先搜尋
使用迴圈遍歷圖的頂點。我們還將使用 stack 來跟蹤 unvisited 頂點。
首先，我們將遍歷根節點並將其推入堆疊。然後，當我們的堆疊不為空時，我們將從堆疊中窺視（讀取最頂層的頂點而不刪除它）一個頂點，如果沒有遍歷該頂點，我們將遍歷它。
然後我們將讀取剛剛遍歷過的頂點的 adjacent vertex，如果我們之前沒有遍歷過它，將它壓入堆疊。
#Python 3.x
def dfs(graph, root_node):
traversed = [root_node]
stack = [root_node]
while stack:
vertex = stack[-1]
if vertex not in traversed:
traversed.extend(vertex)
pop = True
for adjacent in graph[vertex]:
if adjacent not in traversed:
stack.extend(adjacent)
pop = False
break
if pop:
stack.pop()
return traversed
graph = {
'1' : ['5','9'],
'5' : ['2', '4'],
'9' : ['8'],
'2' : ['4'],
'4' : ['2'],
'8' : []
}
print (dfs(graph, '1'))
輸出：
#python 3.x
['1', '5', '2', '4', '9', '8']
我們必須越走越深，到達沒有相鄰頂點的葉節點。我們從 stack 中彈出 leaf nodes，因為不會執行 DFS，我們已經遍歷了它。
所以，for 迴圈並沒有被執行。我們將回溯。
控制再次進入 while 迴圈，併為堆疊的 peek 元素執行 DFS，直到 stack 為空。
I am Fariba Laiq from Pakistan. An android app developer, technical content writer, and coding instructor. Writing has always been one of my passions. I love to learn, implement and convey my knowledge to others.
LinkedIn