基于DFS递归查找字典列表中各键的间接依赖项

给定字典列表：

[{"a": ["b", "c", "d"]},
 {"b": ["e", "z", "g"]},
 {"g": ["c", "f", "z"]},  
 {"z": ["w", "y", "x"]}]

其中：

• "a"直接依赖于"b", "c", "d"；
• "a"间接依赖于"e", "z", "g", "f", "w", "y", "z"，因为其直接依赖项存在这些直接或间接依赖。

现需实现深度优先搜索（DFS）算法，生成包含每个键对应**间接依赖项（排除直接依赖）**的字典列表，预期输出如下：

[{"a": ["e", "z", "g", "f", "w", "y", "z"]},
 {"b": ["c", "f", "w", "y", "x"]},
 {"g": ["w", "y", "x"]},  
 {"z": []}]

实现代码 #

def get_indirect_deps(dep_list):
    # 将输入字典列表合并为单映射字典，便于快速查找
    dep_map = {}
    for d in dep_list:
        dep_map.update(d)
    
    result = []
    for key in dep_map:
        direct_deps = dep_map[key]
        indirect_deps = []
        # 用栈实现DFS遍历
        stack = direct_deps.copy()
        
        while stack:
            current = stack.pop()
            # 若当前节点存在依赖项，将其加入间接依赖列表并继续遍历
            if current in dep_map:
                for dep in dep_map[current]:
                    indirect_deps.append(dep)
                    stack.append(dep)
        # 构造当前键的结果字典并加入列表
        result.append({key: indirect_deps})
    return result

# 测试输入
input_deps = [{"a": ["b", "c", "d"]},
              {"b": ["e", "z", "g"]},
              {"g": ["c", "f", "z"]},  
              {"z": ["w", "y", "x"]}]

# 生成并打印结果
output = get_indirect_deps(input_deps)
for item in output:
    print(item)

代码说明 #

1. 映射转换：把输入的字典列表合并为单个字典dep_map，避免多次遍历列表查找依赖，提升效率。
2. DFS遍历逻辑：以当前键的直接依赖项作为初始栈元素，通过弹出栈顶元素递归遍历其所有依赖项，将这些依赖项全部收集为间接依赖。
3. 结果构造：逐个处理每个键，收集完对应间接依赖后，按输入格式组装成字典列表。

注：代码保留了预期输出中的重复元素（如"a"的间接依赖里重复的"z"），若需去重，可改用集合存储间接依赖项，最后再转为列表。

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