### Python 中图结构的深度优先遍历（DFS）和广度优先遍历（BFS） #### 深度优先搜索（DFS） 在Python中，可以通过递归或者栈来实现深度优先搜索。对于递归方式来说，函数会不断调用自己直到达到终止条件；而基于栈的方式则是显式地使用一个栈来进行节点访问控制。 下面是一个简单的递归版本DFS实现： ```python def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next_node in graph[start] - visited: dfs(graph, next_node, visited) # 继续深入下一个未访问过的邻接点 return visited ``` 此代码片段展示了如何通过递归来执行一次完整的DFS过程[^1]。 另外一种非递归的方法如下所示： ```python def iterative_dfs(graph, start): stack, path = [start], [] while stack: vertex = stack.pop() if vertex not in path: path.append(vertex) # 添加所有相邻且尚未被探索过的新顶点到堆栈顶部 stack.extend(set(graph[vertex]) - set(path)) return path ``` 这段程序利用了一个列表作为LIFO（后进先出）的数据容器——即所谓的“栈”，从而实现了迭代式的DFS操作。 #### 广度优先搜索（BFS） 相比之下，广度优先搜索更适合于寻找最短路径等问题场景下应用。它总是按照层次顺序逐层向外扩展直至找到目标为止。通常情况下我们会借助队列这种FIFO（先进先出）特性明显的数据结构完成这一任务。 这里给出了一种典型的BFS算法实现方案： ```python from collections import deque def bfs(graph, start): queue, visited = deque([start]), {start} while queue: vertex = queue.popleft() # 取出最早进入队列中的元素 print(f'Visiting node: {vertex}') for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return list(visited) ``` 上述例子说明了怎样运用`deque`类创建双向队列并配合集合记录已探查位置以防止重复处理相同结点的情况发生。 当面对实际编程挑战时，选择合适的策略取决于具体需求以及待解决问题本身的性质。有时候结合两者优势也可能带来更好的解决方案，比如采用迭代加深深搜(IDS)[^2]。 为了便于理解和记忆，在涉及二维网格或其他具有固定方向性的场合里，可以定义方向数组辅助移动逻辑[^3]。 最后值得注意的是，无论是哪种类型的遍历模式都可能遇到不同的输入形式如树形结构等特殊情形下的变化形态[^4]。