问题场景描述
在处理图结构或层级依赖数据时，我们常会遇到需要从一个字典中，基于一组起始键（source_list）开始，逐步探索其值所对应的键，直到遇到一组目标值（target_list）为止。同时，要求将每层探索到的键值对按其迭代层级（0、1、2...）组织到一个结果字典中。
考虑以下示例数据：
- source_list：起始节点列表，例如 ['a', 'b']
- target_list：目标节点列表，例如 ['x', 'y', 'z']
- my_dict：表示图结构的字典，键是节点，值是其相邻节点列表。
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']}}一个常见的误区是尝试直接迭代，但这可能无法正确处理层级关系，尤其是在 next_dict 的构建逻辑中，若没有正确追踪已访问节点和层级，可能导致结果不完整或不准确，例如只得到第一层的结果：{0: {'a': ['e'], 'b': ['f', 'd']}}。
广度优先搜索（BFS）原理
解决这类分层探索问题的理想算法是广度优先搜索（BFS）。BFS 是一种用于遍历或搜索树或图的算法。它从图的根（或任意给定节点）开始，首先探索所有相邻节点，然后对于每个相邻节点，再探索其所有相邻节点，以此类推。这种“一层一层”向外扩展的特性，使其非常适合按层级收集数据。
立即学习“Python免费学习笔记（深入）”；
BFS 的核心思想是使用队列（deque）来管理待访问的节点。每次从队列中取出一个节点，访问其所有未访问的邻居，并将这些邻居加入队列。为了避免重复访问和无限循环（在有环图中），通常会使用一个 seen 集合来记录已访问过的节点。
BFS 解决方案一：基础实现
以下是一个基于 BFS 思想的函数 bfs，它能够根据 source_list 和 target_list 从 graph（即 my_dict）中分层提取数据。
from collections import deque
def bfs(source, target, graph):
"""
使用广度优先搜索从图中分层提取数据。
Args:
source (list): 起始节点列表。
target (list): 目标节点列表。
graph (dict): 表示图结构的字典，键为节点，值为其相邻节点列表。
Returns:
dict: 按迭代层级组织的字典，键为层级，值为该层级中的键值对。
"""
# 初始化队列，存储 (层级, 节点) 对
queue = deque((0, node) for node in source)
# 将目标列表转换为集合，以便快速查找
target_set = set(target)
# 记录已访问过的节点，防止重复和循环
seen = set(source) # 初始时，source_list中的节点已被“访问”
result = {}
while queue:
level, node = queue.popleft() # 取出当前层级和节点
# 获取当前节点的邻居，如果节点不在图中，则视为空列表
neighbors = graph.get(node, [])
# 将当前节点及其邻居添加到结果字典的对应层级中
result.setdefault(level, {})[node] = neighbors.copy()
for neighbor in neighbors:
# 如果邻居节点已访问过，或它就是目标节点之一，则跳过
if neighbor in seen or neighbor in target_set:
continue
# 标记邻居节点为已访问
seen.add(neighbor)
# 将邻居节点及其下一层级添加到队列
queue.append((level + 1, neighbor))
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(source_list, target_list, my_dict)
print(output)输出：
{0: {'a': ['e'], 'b': ['f', 'd']},
1: {'e': ['g'], 'f': ['t', 'h'], 'd': ['x']},
2: {'g': ['x'], 't': ['y'], 'h': ['z']}}代码解析：
- queue 初始化：存储元组 (level, node)，level 表示当前节点所在的层级。初始时，source_list 中的所有节点都在第 0 层。
- target_set 和 seen：target_set 用于高效判断节点是否为目标节点。seen 集合用于记录所有已入队或已处理的节点，防止重复处理和陷入循环。
- while queue 循环：BFS 的主循环，当队列非空时持续进行。
- level, node = queue.popleft()：从队列头部取出当前待处理的节点及其层级。
- result.setdefault(level, {})[node] = neighbors.copy()：将当前节点及其邻居添加到 result 字典中对应 level 的子字典里。setdefault 确保 level 键存在。
- 遍历 neighbors：对当前节点的所有邻居进行迭代。
- if neighbor in seen or neighbor in target_set：如果邻居已访问过，或者它就是 target_list 中的一个值，则不将其加入队列，因为我们不需要继续探索这些路径。
- seen.add(neighbor) 和 queue.append((level + 1, neighbor))：将未访问且非目标的邻居标记为已访问，并将其与下一层级 level + 1 一起加入队列。
BFS 解决方案二：优化层级构建
为了更清晰地构建每个层级的结果，可以对 BFS 过程进行优化，将每个层级的节点处理逻辑封装在一个辅助函数中。这种方法通过在一个内部循环中处理完当前层级的所有节点，然后才递增层级计数。
from collections import deque
def solution(source, target, graph):
"""
使用优化的广度优先搜索从图中分层提取数据。
Args:
source (list): 起始节点列表。
target (list): 目标节点列表。
graph (dict): 表示图结构的字典，键为节点，值为其相邻节点列表。
Returns:
dict: 按迭代层级组织的字典，键为层级，值为该层级中的键值对。
"""
target_set = set(target)
result = {}
# 初始时，将source_list中的所有节点标记为已访问，并加入队列
seen = set(source)
queue = deque(source)
level = 0
while queue:
# 构建当前层级的所有键值对
result[level] = build_level_dict(graph, queue, seen, target_set)
level += 1 # 进入下一层
return result
def build_level_dict(graph, queue, seen, target_set):
"""
辅助函数，用于构建当前BFS层级的字典。
"""
# 记录当前层级队列的尾部节点，作为当前层级结束的标志
tail = queue[-1]
level_dict = {}
while True:
node = queue.popleft() # 取出当前层级的节点
# 获取当前节点的邻居，如果节点不在图中，则视为空列表
neighbors = graph.get(node, [])
level_dict[node] = neighbors.copy() # 添加到当前层级字典
for neighbor in neighbors:
# 如果邻居节点已访问过，或它就是目标节点之一，则跳过
if neighbor in seen or neighbor in target_set:
continue
seen.add(neighbor) # 标记邻居节点为已访问
queue.append(neighbor) # 将邻居节点添加到队列，等待下一层处理
if node == tail: # 如果当前节点是本层级的最后一个节点，则本层处理完毕
return level_dict
# 示例调用
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 = solution(source_list, target_list, my_dict)
print(output_optimized)输出：
{0: {'a': ['e'], 'b': ['f', 'd']},
1: {'e': ['g'], 'f': ['t', 'h'], 'd': ['x']},
2: {'g': ['x'], 't': ['y'], 'h': ['z']}}代码解析：
- solution 函数：负责初始化 seen、queue 和 level，并主导层级迭代。
-
build_level_dict 辅助函数：
- 通过 tail = queue[-1] 记录当前层级在队列中的最后一个节点。
- 内部 while True 循环持续从队列中取出节点，直到遇到 tail 节点，表示当前层级的所有节点都已处理完毕。
- 处理逻辑与基础 BFS 类似，将节点的邻居加入队列，并更新 seen 集合。
- 返回构建好的 level_dict。
这种优化版本在某些情况下可能稍微快一些，因为它避免了在队列中存储层级信息（level），而是通过外部循环和 tail 标记来管理层级，从而减少了每次 popleft 和 append 操作的数据量。
注意事项
- 图的类型：如果 my_dict 保证是一个树结构（无环图），那么 seen 集合可以移除，因为不会有重复访问的节点。但在大多数实际应用中，为了健壮性，保留 seen 是一个好习惯，以应对可能存在的循环引用。
- 内存消耗：对于非常大的图，seen 集合和 queue 可能会占用大量内存。需要根据实际情况评估内存使用。
- 目标节点处理：一旦遇到 target_list 中的节点，我们停止沿着该路径继续探索。这意味着 target_list 中的节点本身不会作为键出现在 result 字典的任何层级中，而是作为某个键的“值”出现，并且其子节点不会被进一步探索。
- 键不存在：在获取 neighbors 时，使用了 graph.get(node, [])，这可以优雅地处理 node 不在 graph 中的情况，避免 KeyError。
总结
通过本文的介绍，我们了解了如何利用广度优先搜索（BFS）算法有效地从一个 Python 字典中，根据起始节点和目标节点，分层级地提取和组织数据。无论是基础的 BFS 实现还是通过辅助函数优化层级构建的版本，核心都在于利用队列的先进先出特性和 seen 集合来保证按层级遍历且不重复。这种方法在处理依赖关系、路径查找或层级数据展示等场景中具有广泛的应用价值。
