深度优先搜索是一种流行的图遍历算法。在本教程中，我们将通过示例了解它的工作原理；以及我们如何用 Python 实现它。
我们将研究以下部分：
介绍
图和树是我们在计算机科学中的各种应用中使用的最重要的数据结构。
它们以节点的形式表示数据，节点通过“边”连接到其他节点。
与其他数据结构一样，遍历所有元素或在图或树中搜索元素是定义此类数据结构所需的基本操作之一。深度优先搜索就是这样一种图遍历算法。
深度优先搜索算法
深度优先搜索首先查看图的根节点（任意节点）。如果我们要遍历整个图，它会访问根节点的第一个子节点，然后依次查看该节点的第一个子节点，并继续沿着该分支，直到到达叶节点。
接下来，它以类似的方式回溯并探索父节点的其他子节点。这一直持续到我们访问了树的所有节点，并且没有任何父节点可供探索。
source: 维基百科
但是，如果我们正在执行特定元素的搜索，那么在每一步中，都会与我们当前所在的节点进行比较操作。
如果该元素不存在于特定节点中，则会发生探索每个分支和回溯的相同过程。
这一直持续到图的所有节点都被访问过，或者我们找到了我们正在寻找的元素。
表示一个图
在我们尝试用Python实现DFS算法之前，有必要首先了解如何在Python中表示图。
图表有多种版本。图可能具有两个节点之间的有向边（定义源和目的地）或无向边。节点之间的边可能有也可能没有权重。根据应用程序，我们可以使用图表的各种版本中的任何一个。
为了遍历整个图，我们将使用有向边的图（因为我们需要对节点之间的父子关系进行建模），并且边将没有权重，因为我们关心的是图的完整遍历。
现在，Python 有多种表示图的方法；两种最常见的方式如下：
- 邻接矩阵
- 邻接表
邻接矩阵
邻接矩阵是形状为 N x N 的方阵（其中 N 是图中的节点数）。
每行代表一个节点，每列代表该节点的潜在子节点。
每个（行，列）对代表一个潜在的边缘。
边是否存在取决于矩阵中相应位置的值。
(i,j) 位置处的非零值表示节点 i 和 j 之间存在边，而值为零表示 i 和 j 之间不存在边。
邻接矩阵中的值可以是二进制数或实数。
我们可以在非加权图中使用二进制值（1 表示存在边，0 表示不存在）。
对于实际值，我们可以将它们用于加权图，并表示与表示位置的行和列之间的边缘相关的权重。
例如，位置 (2,3) 处的值 10 表示节点 2 和 3 之间存在承载权重 10 的边。
在Python中，我们可以使用二维邻接矩阵来表示NumPy 数组.
邻接表
邻接表是多个列表的集合。每个列表代表图中的一个节点，并存储该节点的所有邻居/子节点。
在Python中，邻接列表可以使用字典来表示，其中键是图的节点，它们的值是存储这些节点的邻居的列表。
我们将使用这个表示来实现 DFS 算法。
让我们举一个示例图并使用 Python 中的字典来表示它。
给定的图有以下四个边：
- 甲->乙
- A -> C
- 乙 -> 丙
- C -> D
现在让我们用 Python 创建一个字典来表示这个图。
graph = {"A": ["B", "C"],
"B": ["C"],
"C": ["D"]}
现在我们知道了如何在 Python 中表示图，我们可以继续实现 DFS 算法。
实现深度优先搜索（非递归方法）
我们将考虑第一部分动画中显示的图形示例。
让我们使用 Python 字典将此图定义为邻接表。
graph = {"A":["D","C","B"],
"B":["E"],
"C":["G","F"],
"D":["H"],
"E":["I"],
"F":["J"]}
使用 DFS 对该图进行遍历的预期顺序之一是：
让我们实现一个接受图并使用 DFS 遍历它的方法。我们可以使用递归技术以及非递归迭代方法来实现这一点。
在本节中，我们将研究迭代方法。
我们将使用堆栈和列表来跟踪访问过的节点。
我们将从根节点开始，将其附加到路径并将其标记为已访问。然后我们将其所有邻居添加到堆栈中。
在每一步中，我们都会从堆栈中弹出一个元素并检查它是否已被访问。
如果它还没有被访问过，我们会将它添加到路径中，并将其所有邻居添加到堆栈中。
def dfs_non_recursive(graph, source):
if source is None or source not in graph:
return "Invalid input"
path = []
stack = [source]
while(len(stack) != 0):
s = stack.pop()
if s not in path:
path.append(s)
if s not in graph:
#leaf node
continue
for neighbor in graph[s]:
stack.append(neighbor)
return " ".join(path)
我们的用户定义方法将表示图的字典和源节点作为输入。
请注意，源节点必须是字典中的节点之一，否则该方法将返回“无效输入”错误。
让我们在定义的图上调用这个方法，并验证遍历的顺序是否与上图所示的一致。
DFS_path = dfs_non_recursive(graph, "A")
print(DFS_path)
Output :
因此，图的遍历顺序是“深度优先”的方式。
使用递归方法的 DFS
我们可以使用一种称为递归的流行问题解决方法来实现深度优先搜索算法。
递归是一种将同一问题划分为更小的实例，并在其体内递归调用相同方法的技术。
我们将在我们的方法中定义一个基本情况，即“如果叶节点已被访问，我们需要回溯”。
我们来实现该方法：
def recursive_dfs(graph, source,path = []):
if source not in path:
path.append(source)
if source not in graph:
# leaf node, backtrack
return path
for neighbour in graph[source]:
path = recursive_dfs(graph, neighbour, path)
return path
现在我们可以创建我们的图（与上一节相同），并调用递归方法。
graph = {"A":["B","C", "D"],
"B":["E"],
"C":["F","G"],
"D":["H"],
"E":["I"],
"F":["J"]}
path = recursive_dfs(graph, "A")
print(" ".join(path))
Output:
遍历的顺序还是深度优先的方式。
二叉树的深度优先搜索
什么是二叉树？
二叉树是一种特殊的图，其中每个节点只能有两个子节点或没有子节点。
二叉树的另一个重要属性是节点左子节点的值将小于或等于当前节点的值。
同样，右子节点的值大于当前节点的值。
因此，根节点左分支中的每个值都小于根处的值，而右分支中的每个值都将大于根处的值。
让我们了解如何使用 Python 类来表示二叉树。
使用 Python 类表示二叉树
我们可以创建一个类来表示树中的每个节点及其左右子节点。
使用根节点对象，我们可以解析整个树。
我们还将定义一个将新值插入二叉树的方法。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self, value):
if value:
if value < self.value:
if self.left is None:
self.left = Node(value)
else:
self.left.insert(value)
elif value > self.value:
if self.right is None:
self.right = Node(value)
else:
self.right.insert(value)
else:
self.value = value
现在让我们创建一个根节点对象并向其中插入值以构造一棵二叉树，如上一节中的图中所示。
root = Node(7)
root.insert(2)
root.insert(25)
root.insert(9)
root.insert(80)
root.insert(0)
root.insert(5)
root.insert(15)
root.insert(8)
这将构建如上图所示的二叉树。
它还将确保无论我们以什么顺序插入值，都满足二叉树的属性，即“每个节点 2 个子节点”和“左
为二叉树实现 DFS
现在让我们定义一个递归函数，它将根节点作为输入，并按“深度优先搜索”顺序显示树中的所有值。
def dfs_binary_tree(root):
if root is None:
return
else:
print(root.value,end=" ")
dfs_binary_tree(root.left)
dfs_binary_tree(root.right)
我们现在可以调用此方法并传递我们刚刚创建的根节点对象。
dfs_binary_tree(root)
Output:
这种顺序也称为二叉树的“前序遍历”。
使用networkx进行深度优先搜索
到目前为止，我们一直在编写表示图和遍历图的逻辑。
但是，与所有其他重要应用程序一样，Python 也提供了一个处理图形的库。它被称为‘网络x’.
‘networkx’是一个Python包使用节点和边来表示图，并且它提供了多种方法对图执行不同的操作，包括 DFS 遍历。
我们首先看一下如何使用networkx构建一个图。
在networkx中构建图表
为了在networkx中构造一个图，我们首先创建一个图对象，然后使用“add_node()”方法添加图中的所有节点，然后使用“add_edge()”方法定义节点之间的所有边。
让我们使用“networkx”构建下图。
import networkx as nx
G = nx.Graph() #create a graph
G.add_node(1) # add single node
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_node(5)
G.add_nodes_from([6,7,8,9]) #add multiple nodes
现在我们已经添加了所有节点，让我们定义这些节点之间的边，如图所示。
# adding edges
G.add_edge(5,8)
G.add_edge(5,4)
G.add_edge(5,7)
G.add_edge(8,2)
G.add_edge(4,3)
G.add_edge(4,1)
G.add_edge(7,6)
G.add_edge(6,9)
在 DFS 中可视化图形
现在，我们通过定义节点和边构建了图，让我们看看 networkx 的“draw()”方法看起来如何，并验证它是否按照我们想要的方式构建。我们将使用绘图库显示图表。
import matplotlib.pyplot as plt
nx.draw(G, with_labels=True, font_weight='bold')
plt.show()
Output:
方向可能与我们的设计略有不同，但它类似于同一张图，节点之间以及节点之间具有相同的边。
现在让我们对该图执行 DFS 遍历。
Networkx 中的图遍历 – DFS
“networkx”提供了一系列以不同方式遍历图表的方法。我们将使用“dfs_preorder_nodes()”方法以深度优先搜索顺序解析图。
从图中预期的顺序应该是：
5、8、2、4、3、1、7、6、9
让我们调用该方法并查看它以什么顺序打印节点。
dfs_output = list(nx.dfs_preorder_nodes(G, source=5))
print(dfs_output)
Output:
因此，networkx 的遍历顺序符合我们的预期。
现在我们已经很好地理解了深度优先搜索或 DFS 遍历，让我们看看它的一些应用。
使用深度优先搜索进行拓扑排序
拓扑排序是图的重要应用之一，用于对许多现实生活中的问题进行建模，其中任务的开始取决于其他任务的完成。
例如，我们可以使用图的节点来表示许多作业或任务。
某些任务可能依赖于某些其他任务的完成。这种依赖关系是通过建模的有向边节点之间。
具有有向边的图称为有向图。
如果我们想要从这样一组任务中执行调度操作，我们必须确保不违反依赖关系，即任务链中后面出现的任何任务始终仅在其之前的所有任务完成之后执行。
我们可以通过图的拓扑排序来实现这种顺序。
请注意，为了使拓扑排序成为可能，图中必须不存在有向循环，也就是说，该图必须是有向无环图or DAG.
让我们以 DAG 为例，并使用深度优先搜索方法对其执行拓扑排序。
假设上图中的每个节点代表工厂中生产产品的任务。节点模型之间的有向箭头是每个任务对先前任务完成的依赖关系。
因此，无论我们选择执行的任务顺序如何，为了开始任务 C，任务 A 和 E 必须已经完成。
类似地，为了执行任务I，任务A、E、C和F必须已经完成。由于节点 H 上没有向内的箭头，因此任务 H 可以在任何点执行，而不依赖于任何其他任务的完成。
我们可以使用 Python networkx 的“有向图”模块构建这样的有向图。
dag = nx.digraph.DiGraph()
dag.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])
dag.add_edges_from([('A', 'B'), ('A', 'E'), ('B', 'D'), ('E', 'C'),
('D', 'G'),('C', 'G'),('C', 'I'), ('F', 'I')])
请注意，我们使用了方法“add_nodes_from()”和“add_edges_from()”一次性添加有向图的所有节点和边。
我们现在可以编写一个函数来使用 DFS 执行拓扑排序。
我们将从没有向内箭头的节点开始，并继续探索其分支之一，直到到达叶节点，然后回溯并探索其他分支。
一旦我们探索了一个节点的所有分支，我们就会将该节点标记为“已访问”并将其推送到堆栈中。
一旦访问了每个节点，我们就可以在堆栈上执行重复的弹出操作，以给出任务的拓扑排序顺序。
现在让我们将这个想法转化为一个Python函数：
def dfs(dag, start, visited, stack):
if start in visited:
# node and all its branches have been visited
return stack, visited
if dag.out_degree(start) == 0:
# if leaf node, push and backtrack
stack.append(start)
visited.append(start)
return stack, visited
#traverse all the branches
for node in dag.neighbors(start):
if node in visited:
continue
stack, visited = dfs(dag, node, visited, stack)
#now, push the node if not already visited
if start not in visited:
print("pushing %s"%start)
stack.append(start)
visited.append(start)
return stack, visited
def topological_sort_using_dfs(dag):
visited = []
stack=[]
start_nodes = [i for i in dag.nodes if dag.in_degree(i)==0]
# print(start_nodes)
for s in start_nodes:
stack, visited = dfs(dag, s, visited, stack)
print("Topological sorted:")
while(len(stack)!=0):
print(stack.pop(), end=" ")
我们定义了两个函数，一个用于递归遍历节点，另一个主要的拓扑排序函数首先找到所有没有依赖关系的节点，然后使用深度优先搜索方法遍历每个节点。
最后，它从堆栈中弹出值，从而产生节点的拓扑排序。
现在我们调用函数“topological_sort_using_dfs()”
topological_sort_using_dfs(dag)
Output :
如果我们仔细观察输出顺序，我们会发现每当每个作业启动时，它的所有依赖项都会在它之前完成。
我们还可以将其与“networkx”模块中名为“topological_sort()”的拓扑排序方法的输出进行比较。
topological_sorting = nx.topological_sort(dag)
for n in topological_sorting:
print(n, end=' ')
Output:
看起来 networkx 的 sort 方法产生的排序与我们的方法产生的排序相同。
使用 DFS 查找连通分量
图还有另一个重要的属性，称为连通分量。无向图中的连通分量是指一组节点，其中每个顶点通过路径连接到每个其他顶点。
让我们看下面的例子：
在上图中，存在三个连通分量；每个都被标记为粉红色。
让我们用 Python 构建这个图，然后制定一种在其中查找连接组件的方法。
graph = nx.Graph()
graph.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])
graph.add_edges_from([('A', 'B'), ('B', 'E'), ('A', 'E')]) #component 1
graph.add_edges_from([('C', 'D'), ('D', 'H'), ('H', 'F'), ('F', 'C')]) #component 2
graph.add_edge('G','I') #component 3
让我们同时想象一下它。
import matplotlib.pyplot as plt
nx.draw(graph, with_labels=True, font_weight='bold')
plt.show()
Output:
为了使用 DFS 查找连通分量，我们将维护一个名为“visited”的通用全局数组，每次遇到尚未访问过的新变量时，我们都会开始查找它属于哪个连通分量。
我们将该组件中的每个节点标记为“已访问”，因此我们将无法重新访问它来查找另一个连接的组件。
我们将对每个节点重复此过程，调用 DFS 方法从节点查找连通分量的次数将等于图中连通分量的数量。
让我们用 Python 编写这个逻辑并在我们刚刚构建的图上运行它：
def find_connected_components(graph):
visited = []
connected_components = []
for node in graph.nodes:
if node not in visited:
cc = [] #connected component
visited, cc = dfs_traversal(graph, node, visited, cc)
connected_components.append(cc)
return connected_components
def dfs_traversal(graph, start, visited, path):
if start in visited:
return visited, path
visited.append(start)
path.append(start)
for node in graph.neighbors(start):
visited, path = dfs_traversal(graph, node, visited, path)
return visited, path
让我们在上一步中构建的图表上使用我们的方法。
connected_components = find_connected_components(graph)
print("Total number of connected components =", len(connected_components))
for cc in connected_components:
print(cc)
Output:
结论
在这篇博客中，我们了解了 DFS 算法并以不同的方式使用它。
我们首先了解如何使用常见的数据结构来表示图，并在 Python 中实现它们。
然后，我们使用递归和非递归方法实现深度优先搜索遍历算法。
接下来，我们研究了一种称为二叉树的特殊形式的图，并在其上实现了 DFS 算法。
在这里，我们使用由我们定义的代表节点的 Python 类构造的节点对象来表示整个树。
然后我们研究了 Python 提供的用于表示图形并对其执行操作的产品——“networkx”模块。
我们用它来构建一个图，将其可视化，并在其上运行我们的 DFS 方法。我们将输出与模块自己的 DFS 遍历方法进行了比较。
最后，我们研究了深度优先搜索遍历的两个重要应用，即拓扑排序和查找图中的连通分量。
