使用广度优先搜索（BFS）按层级提取Python字典数据

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']}}

from collections import deque

def bfs(source, target, graph):
    """
    使用广度优先搜索（BFS）按层级提取字典数据。

    Args:
        source (list): 起始节点列表。
        target (list): 目标节点列表。当邻居节点中包含目标节点时，停止进一步探索。
        graph (dict): 表示图的字典，键是节点，值是其邻居列表。

    Returns:
        dict: 结构化输出，键为层级（迭代次数），值为该层级中所有被访问节点及其邻居的子字典。
    """
    # 初始化队列，存储 (层级, 节点) 对
    queue = deque((0, node) for node in source)
    # 将目标列表转换为集合，以便进行O(1)的快速查找
    target_set = set(target)
    # 记录已访问过的节点，防止循环和重复处理
    seen = set(source) # 初始时，source_list中的节点已被视为“已访问”

    result = {} # 存储最终结果

    while queue:
        level, node = queue.popleft() # 取出当前层级和节点

        # 确保当前节点在图中存在，避免KeyError
        if node not in graph:
            continue

        neighbors = graph[node] # 获取当前节点的邻居

        # 将当前节点及其邻居添加到结果字典中对应层级
        # setdefault确保如果层级不存在，则创建一个空字典
        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']
}

# 运行BFS函数
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']}}

from collections import deque

def solution(source, target, graph):
    """
    优化版BFS，按层级构建结果。

    Args:
        source (list): 起始节点列表。
        target (list): 目标节点列表。
        graph (dict): 表示图的字典。

    Returns:
        dict: 结构化输出，键为层级，值为该层级中所有被访问节点及其邻居的子字典。
    """
    target_set = set(target)
    result = {}

    # seen集合在初始化时就包含所有source节点，避免重复添加到队列
    seen = set(source)
    # 队列初始化为所有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):
    """
    辅助函数，用于构建当前层级的字典。
    在内部循环中处理队列中当前层级的所有节点。
    """
    # 记录当前层级队列的末尾节点，用于判断何时结束当前层级的处理
    # 注意：如果queue为空，此操作会报错。在solution函数中已确保queue非空。
    tail = queue[-1] 
    level_dict = {} # 存储当前层级的节点及其邻居

    while True:
        node = queue.popleft() # 取出当前节点

        # 确保当前节点在图中存在
        if node not in graph:
            # 如果节点不存在，但它在当前层级被处理，我们仍然需要记录它为空
            # 或者选择跳过，取决于具体需求。这里选择跳过。
            if node == tail: # 如果是当前层级的最后一个节点，需要跳出循环
                return level_dict
            continue # 跳过不存在的节点

        neighbors = graph[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']}}