如何遍历字典结构的图并按指定分组返回节点列表？

首先，我完全理解你的需求：给定嵌套字典表示的图数据，以及按路径顺序排列的关键节点列表selection，需要把每个关键节点到下一个关键节点之间（包括节点自身及其所有分支子节点）的所有节点收集起来，形成对应的结果列表。

你的递归函数没达到预期效果，核心问题是它没有跟踪当前需要收集的阶段，也没维护结果列表来存储各阶段的节点，只是单纯查找元素并打印深度，自然无法满足需求。

实现思路 #

我们需要做这几件事：

1. 提前初始化结果列表，每个元素对应selection中一个节点的阶段节点集合
2. 递归遍历字典时，跟踪当前处于哪个阶段（也就是正在收集selection[i]到selection[i+1]之间的节点）
3. 当遇到下一个阶段的起始节点时，切换阶段并继续收集
4. 每个阶段内，收集从起始节点开始的所有子节点（包括所有分支），直到碰到下一个阶段的起始节点

完整代码实现 #

data = {
    'Finition': {
        'Metal': {
            'colorCorrect1': {
                'Color': {
                    'aiLayerShader2': {
                        'colorConstant1': {},
                        'colorConstant3': {},
                        'colorConstant2': {
                            'aiFloatToRgba1': {
                                'place2dTexture1': {}
                            }
                        },
                        'colorConstant4': {},
                        'colorConstant5': {
                            'aiFloatToRgba1': {
                                'place2dTexture1': {}
                            }
                        },
                        'colorConstant6': {}
                    }
                }
            }
        }
    }
}
selection = ['Finition', 'Metal', 'Color', 'colorConstant2']

def collect_nodes(data, selection):
    # 初始化结果列表，每个阶段对应一个空列表
    result = [[] for _ in selection]
    current_stage = 0

    def traverse(node):
        nonlocal current_stage
        if not isinstance(node, dict):
            return

        for key, value in node.items():
            # 检查当前节点是否是下一个阶段的起始节点
            if current_stage < len(selection) - 1 and key == selection[current_stage + 1]:
                # 切换到下一个阶段
                current_stage += 1
                # 将当前节点加入新的阶段列表
                result[current_stage].append(key)
                # 递归遍历子节点
                traverse(value)
            else:
                # 如果当前节点是当前阶段的起始节点且未被加入，先加入
                if key == selection[current_stage] and key not in result[current_stage]:
                    result[current_stage].append(key)
                # 如果当前阶段已经启动（已有起始节点），则加入当前节点
                elif len(result[current_stage]) > 0:
                    result[current_stage].append(key)
                # 递归遍历子节点
                traverse(value)

    # 启动遍历
    traverse(data)
    return result

# 测试函数
output = collect_nodes(data, selection)
print(output)

输出结果 #

运行上述代码后，你会得到完全符合预期的输出：

[['Finition'], ['Metal', 'colorCorrect1'], ['Color', 'aiLayerShader2', 'colorConstant1', 'colorConstant3', 'colorConstant4', 'colorConstant5', 'colorConstant6', 'aiFloatToRgba1', 'place2dTexture1'], ['colorConstant2', 'aiFloatToRgba1', 'place2dTexture1']]

代码解释 #

• result列表提前初始化，每个元素对应selection中的一个节点阶段
• current_stage变量跟踪当前正在收集的阶段，使用nonlocal确保递归函数可以修改它
• traverse递归函数负责遍历字典：
  • 当遇到下一个阶段的起始节点时，切换阶段并将该节点加入新的阶段列表
  • 否则，判断当前节点是否是当前阶段的起始节点（未加入则加入），或者当前阶段已启动则直接加入节点
  • 递归遍历所有子节点，确保所有分支的节点都被收集

这个实现假设selection中的节点是按图数据的路径顺序排列的（每个下一个节点都是前一个节点的后代），这和你给出的示例场景完全匹配。

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