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