在数据结构与算法的广阔天地中，图（Graph）作为一种能够表示复杂关系的数据结构，扮演着举足轻重的角色。而图的遍历，尤其是深度优先搜索（DFS, Depth-First Search）和广度优先搜索（BFS, Breadth-First Search），则是解决图相关问题的两大基本且强大的工具。今天，我们将通过Python语言，深度挖掘这两种遍历方式的艺术，以实际案例展示它们如何让复杂问题迎刃而解。
案例背景：迷宫探索
设想你是一位勇敢的探险家，面前是一座错综复杂的迷宫，你需要找到从入口到出口的最短路径。迷宫可以自然地抽象为一个图，其中每个房间是节点，房间之间的通道是边。现在，让我们用DFS和BFS来分别解决这个问题。
DFS：深入探索，直到无路可走
DFS的核心思想是沿着一条路径尽可能深地搜索，直到达到图的尽头（即无法继续前行的节点），然后回溯到上一个节点，尝试另一条路径。在迷宫问题中，这类似于你不断尝试走进更深的房间，直到死胡同，再返回上一个房间尝试其他门。
python
def dfs(graph, start, end, visited=None):
if visited is None:
visited = set()
visited.add(start)
if start == end:
return [start]
for next_node in graph[start]:
if next_node not in visited:
path = dfs(graph, next_node, end, visited)
if path:
return [start] + path
return []
示例迷宫图（邻接表表示）
maze = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F', 'G'],
'F': ['C', 'E'],
'G': ['E']
}
假设起点为'A'，终点为'G'
path = dfs(maze, 'A', 'G')
print("DFS路径:", path)
BFS：层层推进，逐层遍历
BFS则是从起点开始，逐层向外扩展，直到找到目标节点。在迷宫中，这相当于你站在入口，先查看所有能直接到达的房间，再查看从这些房间能直接到达的下一个房间，依此类推，直到找到出口。
python
from collections import deque
def bfs(graph, start, end):
queue = deque([[start]])
visited = set([start])
while queue:
path = queue.popleft()
node = path[-1]
if node == end:
return path
for next_node in graph[node]:
if next_node not in visited:
visited.add(next_node)
queue.append(path + [next_node])
return []
使用相同的迷宫图
path = bfs(maze, 'A', 'G')
print("BFS路径:", path)
总结
无论是DFS还是BFS，都是解决图遍历问题的有力工具。DFS适用于需要找到所有可能解或深度优先的场景，而BFS则更适用于寻找最短路径或最少步骤的问题。在迷宫探索这个案例中，BFS直接给出了从起点到终点的最短路径，而DFS虽然也能找到路径，但可能不是最短的。通过这两种遍历方式的学习与实践，我们能够更加灵活地应对各种复杂的图结构问题。
