Python图的遍历算法详解（从零开始掌握DFS与BFS）

表示图的数据结构

在Python中，我们通常使用邻接表来表示图。邻接表是一个字典，键是节点，值是该节点连接的所有邻居节点列表。

# 示例：一个无向图的邻接表表示graph = {    'A': ['B', 'C'],    'B': ['A', 'D', 'E'],    'C': ['A', 'F'],    'D': ['B'],    'E': ['B', 'F'],    'F': ['C', 'E']}

深度优先搜索（DFS）

深度优先搜索（DFS）是一种沿着一条路径尽可能深入地访问节点，直到无法继续为止，然后回溯并尝试其他路径的遍历方式。它通常使用递归或栈实现。

下面是一个使用递归实现的DFS代码：

def dfs_recursive(graph, node, visited=None):    if visited is None:        visited = set()        visited.add(node)    print(node, end=' ')  # 打印当前访问的节点        for neighbor in graph[node]:        if neighbor not in visited:            dfs_recursive(graph, neighbor, visited)        return visited# 调用示例graph = {    'A': ['B', 'C'],    'B': ['A', 'D', 'E'],    'C': ['A', 'F'],    'D': ['B'],    'E': ['B', 'F'],    'F': ['C', 'E']}dfs_recursive(graph, 'A')  # 输出: A B D E F C

广度优先搜索（BFS）

广度优先搜索（BFS）则是一层一层地遍历图，先访问离起始节点最近的所有节点，再逐步向外扩展。它通常使用队列（queue）来实现。

以下是使用Python内置deque实现的BFS代码：

from collections import dequedef bfs(graph, start):    visited = set()    queue = deque([start])    visited.add(start)        while queue:        node = queue.popleft()        print(node, end=' ')  # 打印当前访问的节点                for neighbor in graph[node]:            if neighbor not in visited:                visited.add(neighbor)                queue.append(neighbor)        return visited# 调用示例bfs(graph, 'A')  # 输出: A B C D E F

DFS vs BFS：如何选择？

• DFS适合用于寻找路径、检测环、拓扑排序等问题，内存占用相对较小（但递归过深可能导致栈溢出）。
• BFS适合用于寻找最短路径（在无权图中）、层级遍历等场景，但需要更多内存存储队列。

总结

通过本教程，你已经掌握了Python图遍历的两种核心方法：深度优先搜索（DFS）和广度优先搜索（BFS）。这些图算法教程中的基础技能，是你进一步学习更复杂图论问题（如最短路径、最小生成树等）的基石。

建议你动手运行上面的代码，修改图的结构，观察输出结果的变化。实践是最好的老师！

如果你觉得这篇文章对你有帮助，欢迎分享给更多正在学习Python图遍历和图算法教程的朋友！