1. 问题背景与目标
在处理复杂数据结构时，我们常会遇到需要从一个具有层级或图状关系的字典中，根据特定规则提取信息的情况。假设我们有一个表示有向图的字典my_dict，其中键是节点，值是其直接邻居节点列表。我们还定义了一个source_list作为起始节点集，以及一个target_list作为终止节点集。我们的目标是，从source_list中的每个节点开始，逐层遍历my_dict，直到遇到target_list中的任一节点为止。同时，我们希望将每次遍历层级（迭代）所发现的节点及其邻居组织成一个字典，最终输出一个以迭代次数为键的嵌套字典。
例如，给定以下数据：
source_list = ['a', 'b']
target_list = ['x', 'y', 'z']
my_dict = {
'a': ['e'],
'b': ['f', 'd'],
'e': ['g'],
'f': ['t', 'h'],
'd': ['x'],
'g': ['x'],
't': ['y'],
'h': ['z']
}期望的输出是：
{0: {'a': ['e'], 'b': ['f', 'd']},
1: {'e': ['g'], 'f': ['t', 'h'], 'd': ['x']},
2: {'g': ['x'], 't': ['y'], 'h': ['z']}}这里，键0代表第一层迭代，包含从source_list直接可达的节点及其邻居；键1代表第二层迭代，包含从第一层节点可达的节点及其邻居，以此类推。
2. 为什么选择广度优先搜索（BFS）？
最初尝试的解决方案可能使用简单的循环结构，但往往难以正确地管理层级关系并按期望的迭代次数组织输出。这种按层级（或深度）遍历数据结构的需求，正是广度优先搜索（BFS）算法的典型应用场景。
立即学习“Python免费学习笔记（深入）”；
BFS是一种用于遍历或搜索树或图的算法。它从图的某个节点开始，首先访问其所有邻居节点，然后访问这些邻居节点的邻居，依此类推。换句话说，它会先访问距离起始节点“最近”的所有节点，然后再访问距离次之的节点，确保了按层级（或迭代）进行探索。这与我们的需求完美契合，因为我们需要精确地记录每一层迭代所发现的节点。
3. 基于BFS的解决方案实现
我们将介绍两种基于BFS的实现方式。
3.1 基础BFS实现
此实现使用collections.deque作为队列，以高效地管理待访问节点。它通过在队列中存储(level, node)元组来跟踪当前节点的层级。
from collections import deque
def bfs_fetch_by_level(source_nodes, target_nodes, graph_dict):
"""
使用广度优先搜索从字典中按层级提取数据。
Args:
source_nodes (list): 起始节点列表。
target_nodes (list): 目标节点列表。
graph_dict (dict): 表示图结构的字典，键为节点，值为其邻居列表。
Returns:
dict: 按层级组织的提取结果字典。
"""
queue = deque((0, node) for node in source_nodes) # 队列存储 (层级, 节点)
target_set = set(target_nodes) # 目标节点集合，用于快速查找
seen = set(source_nodes) # 已访问节点集合，防止重复访问和循环
result = {} # 存储最终结果
while queue:
level, current_node = queue.popleft() # 取出当前层级和节点
# 获取当前节点的邻居，如果不存在则为空列表
neighbors = graph_dict.get(current_node, [])
# 将当前节点及其邻居添加到结果字典的对应层级中
result.setdefault(level, {})[current_node] = neighbors[:] # 使用[:]进行浅拷贝，避免修改原始列表
for neighbor in neighbors:
# 如果邻居节点已访问过或在目标列表中，则跳过
# 如果在目标列表中，我们不希望继续探索其子节点，因为已达到目标
if neighbor in seen or neighbor in target_set:
continue
seen.add(neighbor) # 标记为已访问
queue.append((level + 1, neighbor)) # 将邻居加入队列，层级加1
return result
# 示例使用
source_list = ['a', 'b']
target_list = ['x', 'y', 'z']
my_dict = {
'a': ['e'],
'b': ['f', 'd'],
'e': ['g'],
'f': ['t', 'h'],
'd': ['x'],
'g': ['x'],
't': ['y'],
'h': ['z']
}
output_bfs = bfs_fetch_by_level(source_list, target_list, my_dict)
print(output_bfs)输出：
{0: {'a': ['e'], 'b': ['f', 'd']}, 1: {'e': ['g'], 'f': ['t', 'h'], 'd': ['x']}, 2: {'g': ['x'], 't': ['y'], 'h': ['z']}}代码解析：
- deque初始化： 队列中存储的是(层级, 节点)元组。起始节点都在第0层。
- target_set与seen： target_set用于快速判断一个节点是否为目标节点。seen集合用于记录已访问过的节点，防止重复处理和陷入图中的循环。
- while queue循环： BFS的核心循环，当队列非空时持续进行。
- result.setdefault(level, {})[current_node] = neighbors[:]： 这行代码巧妙地构建了输出。setdefault(level, {})确保result字典中存在当前level的键，并将其值初始化为一个空字典（如果不存在）。然后，将current_node作为键，其邻居列表作为值添加到这个内部字典中。使用neighbors[:]创建邻居列表的浅拷贝，避免原始graph_dict的意外修改。
-
邻居遍历与条件判断： 对于每个邻居，我们检查它是否已经访问过 (neighbor in seen) 或者它是否是目标节点 (neighbor in target_set)。如果满足任一条件，我们就不再深入探索这个邻居，因为：
- 如果已访问，继续探索会形成循环或重复路径。
- 如果是目标节点，我们已达到该路径的终点，无需再将其子节点加入队列。
- queue.append((level + 1, neighbor))： 将未访问且非目标节点的邻居加入队列，并将其层级设置为当前层级加一。
3.2 优化层级构建的BFS实现
第二种实现方式在构建每一层结果时略有不同，它通过一个内部循环来确保当前层的所有节点都被处理完毕，然后才递增层级。这种方式可能在某些情况下更清晰地表达层级概念。
from collections import deque
def build_level_dict(graph, queue, seen, target_set):
"""
辅助函数：构建当前层级的字典。
"""
# 记录当前层级的最后一个节点，用于判断何时结束本层处理
current_level_end_node = queue[-1] if queue else None
level_dict = {}
while True:
node = queue.popleft()
neighbors = graph.get(node, [])
level_dict[node] = neighbors[:]
for neighbor in neighbors:
if neighbor in seen or neighbor in target_set:
continue
seen.add(neighbor)
queue.append(neighbor)
if node == current_level_end_node: # 当前层所有节点已处理完毕
return level_dict
def optimized_bfs_fetch_by_level(source_nodes, target_nodes, graph_dict):
"""
优化版广度优先搜索，按层级提取数据。
"""
target_set = set(target_nodes)
result = {}
# 初始已访问节点包含源节点
seen = set(source_nodes)
queue = deque(source_nodes) # 队列只存储节点，层级通过外部循环管理
level = 0
while queue:
# 调用辅助函数构建当前层级的结果
result[level] = build_level_dict(graph_dict, queue, seen, target_set)
level += 1 # 层级递增
return result
# 示例使用
source_list = ['a', 'b']
target_list = ['x', 'y', 'z']
my_dict = {
'a': ['e'],
'b': ['f', 'd'],
'e': ['g'],
'f': ['t', 'h'],
'd': ['x'],
'g': ['x'],
't': ['y'],
'h': ['z']
}
output_optimized_bfs = optimized_bfs_fetch_by_level(source_list, target_list, my_dict)
print(output_optimized_bfs)输出：
{0: {'a': ['e'], 'b': ['f', 'd']}, 1: {'e': ['g'], 'f': ['t', 'h'], 'd': ['x']}, 2: {'g': ['x'], 't': ['y'], 'h': ['z']}}代码解析：
- queue初始化： 队列中只存储节点，不再存储层级元组。
- seen初始化： 在开始时就将source_nodes加入seen，表示这些节点已“访问”或“处理”，避免重复从它们开始。
-
build_level_dict函数： 这是核心优化点。它接收graph、queue、seen和target_set。
- current_level_end_node = queue[-1]：在处理当前层级之前，记录队列中最后一个节点。这样，当popleft()取出的节点是这个current_level_end_node时，就意味着当前层的所有节点都已处理完毕。
- 内部while True循环：持续从队列中取出节点，构建level_dict，并将其邻居加入队列。
- if node == current_level_end_node: return level_dict：当处理到当前层的最后一个节点时，返回构建好的level_dict。
- optimized_bfs_fetch_by_level主函数： 外部while queue循环负责管理层级level，每次循环调用build_level_dict来构建当前层的结果。
4. 注意事项与总结
- 图的表示： 这里的my_dict本质上是一个邻接列表表示的图。键是节点，值是其直接可达的邻居节点列表。
- deque的优势： collections.deque（双端队列）相比于普通Python列表，在两端添加和删除元素（如popleft()）时具有O(1)的时间复杂度，这对于BFS算法的性能至关重要。
- seen集合的重要性： seen集合是防止无限循环和重复计算的关键，尤其是在处理可能包含循环的图时。如果您的my_dict保证是一个树结构（无循环），那么seen集合可以简化或移除，但通常保留它更为安全。
- target_set： 将target_nodes转换为set可以使查找操作（neighbor in target_set）的平均时间复杂度从O(N)降低到O(1)，提高效率。
- 浅拷贝neighbors[:]： 在将邻居列表赋值给结果字典时，使用[:]进行浅拷贝是一个好习惯，可以避免在后续操作中无意修改原始graph_dict中的列表。
- 算法复杂度： BFS的时间复杂度通常是O(V + E)，其中V是图中的顶点数，E是边数。空间复杂度是O(V)，用于存储队列和seen集合。
通过这两种基于广度优先搜索的实现，我们能够有效地从复杂的嵌套字典结构中，按照指定的起始节点和目标节点，按层级迭代地提取所需数据，并以清晰的结构化格式呈现。这种方法不仅适用于本例中的特定场景，也广泛应用于各种图遍历和最短路径查找问题。
