使用广度优先搜索（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_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']}}

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