Python字典分层数据提取与广度优先搜索（BFS）应用实践

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_levels(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)

    # 将目标节点转换为集合，以便O(1)时间复杂度进行查找
    target_set = set(target_nodes)

    # 记录已访问的节点，防止重复和循环
    seen = set(source_nodes) # 初始节点也被视为已访问

    # 存储最终结果
    result = {}

    while queue:
        level, current_node = queue.popleft()

        # 获取当前节点的邻居
        neighbors = graph_dict.get(current_node, [])

        # 将当前节点及其邻居添加到结果字典的对应层级中
        # 使用 setdefault 确保层级键存在
        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))

    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_fetch_levels(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 build_level_dict(graph, queue, seen, target_set):
    """
    辅助函数：构建当前层级的字典，并将下一层级的节点加入队列。
    """
    level_dict = {}

    # 记录当前层级队列的末尾，以便知道何时完成当前层级的处理
    # 注意：这里假设queue在调用前已经包含了当前层级的所有节点
    # 并且在处理过程中，新节点会被添加到queue的末尾，不会干扰当前层级的判断
    current_level_size = len(queue) 

    for _ in range(current_level_size): # 遍历当前层级的所有节点
        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) # 新节点加入队列末尾

    return level_dict

def bfs_fetch_levels_optimized(source_nodes, target_nodes, graph_dict):
    """
    优化版的广度优先搜索，分层提取数据。
    在每一轮循环中处理整个层级。
    """
    target_set = set(target_nodes)
    result = {}

    # 初始节点被视为已访问，并加入队列
    seen = set(source_nodes)
    queue = deque(source_nodes)

    level = 0
    while queue:
        # 调用辅助函数处理当前层级的所有节点
        # build_level_dict 会返回当前层级的字典，并将下一层级的节点加入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_fetch_levels_optimized(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']}}