python通过递归实现图的广度优先遍历

在Python中，广度优先遍历（Breadth-First Search, BFS）通常可以使用队列来实现，因为BFS需要按照节点的距离顺序依次访问。然而，如果要在递归的方式下实现BFS，虽然不如常规的非递归方式直观，但是理论上也是可行的。下面是一个简单的递归BFS算法的例子，假设我们有一个表示图邻接关系的字典（Adjacency List），其中键是节点，值是其邻居列表：

from collections import defaultdict

def bfs_recursive(graph, start):
    visited = set()  # 用于跟踪已访问过的节点
    queue = [start]  # 队列初始只放起点

    def recursive_bfs(node):
        if node not in visited:
            visited.add(node)  # 标记节点已访问
            for neighbor in graph[node]:
                recursive_bfs(neighbor)  # 对未访问的邻居递归调用
                queue.append(neighbor)  # 添加邻居到队列

    recursive_bfs(start)
    return list(visited)

# 使用示例
graph = defaultdict(list)  # 示例图：A -> B, C; B -> D; C -> E
graph['A'].append('B')
graph['A'].append('C')
graph['B'].append('D')
graph['C'].append('E')

bfs_order = bfs_recursive(graph, 'A')  # 从'A'开始遍历
print(bfs_order)  # 输出: ['A', 'C', 'B', 'D', 'E']

在这个递归实现中，`recursive_bfs`函数负责实际的遍历工作，它首先检查节点是否已经被访问过，然后对每个未访问的邻居递归调用自身，并将其添加到队列中。由于递归栈的限制，这种方法对于大规模图可能会导致堆栈溢出，因此在实践中一般还是推荐使用非递归的队列版本。