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_extract_levels(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)  # 记录已访问节点，防止循环和重复处理
    result = {}  # 存储最终结果

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

        # 确保当前层级的字典已初始化
        result.setdefault(level, {})

        # 提取当前节点的邻居
        neighbors = graph.get(node, [])
        result[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_extract_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):
    """
    辅助函数：构建当前层级的字典。
    """
    # 标记当前层级队列的末尾，以便知道何时停止处理当前层级
    # 注意：这里假设queue在传入时已经包含了当前层级的所有节点
    # 且这些节点在seen中已标记。
    tail_of_current_level = queue[-1] if queue else None 
    level_dict = {}

    while True:
        if not queue: # 如果队列为空，且没有tail，说明已经处理完所有
            break

        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_of_current_level:
            return level_dict
    return level_dict # 如果队列为空，直接返回

def bfs_optimized_extract_levels(source, target, graph):
    """
    使用优化后的广度优先搜索从图中按层级提取数据。
    每次循环处理一个完整的层级。
    """
    target_set = set(target)
    result = {}

    # 初始层级的所有节点都标记为已访问，并加入队列
    seen = set(source)
    queue = deque(source)
    level = 0

    while queue:
        # 调用辅助函数构建当前层级的字典
        result[level] = build_level_dict(graph, 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_extract_levels(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']}}