Python实现JSON格式图指定节点全层级关联节点的遍历

这个需求本质是有向图的层级遍历场景，要满足“按层级顺序输出关联节点”的要求，用广度优先搜索（BFS）实现最简便，不需要引入第三方图计算依赖：

• 先将原始边列表转换为邻接表结构，把“查询某节点所有关联关系”的复杂度从全量扫描的O(n)降到O(1)，处理大规模图数据时效率提升明显
• 遍历过程中维护已访问节点集合，避免图中存在环路（比如A指向B、B指回A）时出现无限循环
• 用队列缓存每一层待处理的节点，逐层提取关联节点加入结果列表，天然匹配层级遍历的输出规则

# 原始边列表数据
edge_list = [
    {"NodeId":"1","N":"2"},
    {"NodeId":"1","N":"3"},
    {"NodeId":"3","N":"5"},
    {"NodeId":"5","N":"6"},
    {"NodeId":"2","N":"4"},
    {"NodeId":"9","N":"7"}
]

# 构建邻接表：key为源节点ID，value为该节点直接关联的目标节点列表
adjacency = {}
for edge in edge_list:
    src_node = edge["NodeId"]
    dst_node = edge["N"]
    if src_node not in adjacency:
        adjacency[src_node] = []
    adjacency[src_node].append(dst_node)

def get_all_related_nodes(start_node: str) -> list:
    # 起始节点不存在于邻接关系中时直接返回空列表
    if start_node not in adjacency:
        return []
    
    visited = set()
    visited.add(start_node)
    queue = [start_node]
    result = []

    while queue:
        # 取出队首的当前处理节点
        current_node = queue.pop(0)
        # 遍历当前节点的所有直接关联节点
        for neighbor in adjacency.get(current_node, []):
            # 仅处理未访问过的关联节点
            if neighbor not in visited:
                result.append(neighbor)
                visited.add(neighbor)
                queue.append(neighbor)
    return result

# 测试起始节点为"1"的场景
print(get_all_related_nodes("1"))
# 实际输出: ['2', '3', '4', '5', '6']
# 与示例输出的差异仅为同层级节点的排列顺序，层级关系完全符合要求：
# 第一层（直接关联1的节点）：2、3
# 第二层（关联节点的直接关联节点）：4、5
# 第三层：6

• 同一层级内的节点排列顺序可灵活调整：如果需要匹配示例中5排在4前面的顺序，只需在遍历邻接节点前对邻居列表做对应排序即可，不影响层级输出的正确性
• 已访问去重逻辑不可省略：如果图结构存在循环关联，没有去重会导致遍历进入死循环
• 若需要明确区分每个节点所属的层级，可将队列存储的元素从单纯节点ID改为(节点ID, 层级)的元组，遍历过程中即可按层级拆分输出，不需要修改核心遍历逻辑

内容的提问来源于stack exchange，提问作者Milad