深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法
这个算法会尽可能深地搜索图的分支
当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点
这一过程一直进行到已发现从源节点可达的所有节点为止
如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止
下面是一个简单的Python实现，用于在图中执行深度优先搜索：python复制from collections import defaultdictclass Graph: def __init__(self): # 使用字典来表示图 # 键是节点，值是一个列表，包含与该节点相邻的节点 self.graph = defaultdict(list) def add_edge(self, u, v): # 添加一条从u到v的边 self.graph[u].append(v) def DFS(self, v, visited): # 标记当前节点为已访问 visited.add(v) print(v, end=' ') # 遍历当前节点的所有邻居 for neighbor in self.graph[v]: # 如果邻居节点没有被访问过，则递归访问 if neighbor not in visited: self.DFS(neighbor, visited) def DFS_from_node(self, node): # 从给定节点开始深度优先搜索 visited = set() self.DFS(node, visited)# 创建一个图g = Graph()# 添加边g.add_edge(0, 1)g.add_edge(0, 2)g.add_edge(1, 2)g.add_edge(2, 0)g.add_edge(2, 3)g.add_edge(3, 3)print("深度优先搜索（从节点2开始）:")g.DFS_from_node(2)在上面的代码中，我们定义了一个Graph类，其中包含了添加边和执行深度优先搜索的方法
DFS方法是一个递归函数，它首先标记当前节点为已访问，然后遍历当前节点的所有邻居
如果邻居节点还没有被访问过，则递归地对该邻居节点执行相同的操作
请注意，在实际应用中，深度优先搜索可能需要额外的逻辑来处理特定的搜索需求，例如寻找路径、检测环等
此外，为了避免重复访问节点，我们使用了visited集合来跟踪已经访问过的节点
在上面的例子中，我们创建了一个简单的图，并从节点2开始进行深度优先搜索
输出将显示从节点2开始可以访问到的所有节点的顺序