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

什么是图？

图由节点（顶点）和边组成。例如，城市之间的航班网络就是一个图：每个城市是节点，每条航线是边。

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

1. 深度优先搜索（DFS）

DFS 的思想是：从一个起点出发，沿着一条路径尽可能深入，直到无法继续为止，然后回溯并尝试其他路径。它像走迷宫时“一条路走到黑”。

Python实现DFS（递归版）

def dfs_recursive(graph, node, visited):    if node not in visited:        print(node)  # 访问当前节点        visited.add(node)        for neighbor in graph[node]:            dfs_recursive(graph, neighbor, visited)# 示例图graph = {    'A': ['B', 'C'],    'B': ['D', 'E'],    'C': ['F'],    'D': [],    'E': ['F'],    'F': []}visited = set()dfs_recursive(graph, 'A', visited)

Python实现DFS（栈迭代版）

def dfs_iterative(graph, start):    visited = set()    stack = [start]        while stack:        node = stack.pop()        if node not in visited:            print(node)            visited.add(node)            # 将邻居逆序压入栈，保证输出顺序与递归一致            for neighbor in reversed(graph[node]):                if neighbor not in visited:                    stack.append(neighbor)# 调用示例dfs_iterative(graph, 'A')

2. 广度优先搜索（BFS）

BFS 的思想是：从起点开始，先访问所有直接邻居，再访问邻居的邻居，一层一层向外扩展。它像水波扩散一样。

Python实现BFS

from collections import dequedef bfs(graph, start):    visited = set()    queue = deque([start])        while queue:        node = queue.popleft()        if node not in visited:            print(node)            visited.add(node)            for neighbor in graph[node]:                if neighbor not in visited:                    queue.append(neighbor)# 调用示例bfs(graph, 'A')

DFS vs BFS：如何选择？

• DFS 适合用于：寻找路径、检测环、拓扑排序等。
• BFS 适合用于：求最短路径（无权图）、层级遍历、社交网络中的“六度空间”问题。

总结

通过本教程，你已经掌握了Python图遍历的两种核心方法：深度优先搜索DFS和广度优先搜索BFS。它们是解决更复杂图论问题（如最短路径、连通性分析）的基石。建议你动手运行上面的代码，修改图结构，观察输出结果，加深理解。

掌握这些基础算法，是你迈向高级图算法教程的第一步！