如何适配DFS算法获取特殊结构有向图的所有变量路径与注释？

问题分析 #

你的图结构是类型→变量列表，每个变量关联下一个类型和注释，需要DFS遍历从起始类型出发的所有变量路径，遇到none则终止。原代码的核心问题：

• 遍历字典时键值搞反：graph[currentVertex]的键是变量名，值是[目标类型, 注释]，原代码把变量名当成了类型名，逻辑完全颠倒
• 回溯逻辑错误：终止时的pop操作多余，递归传参用visited.copy()导致回溯失效，部分路径无法正确截断

正确实现 #

1. 获取所有变量路径 #

graph = {
    'type1': {'varname1': ['type2', 'comment1'], 'varname7': ['none', 'comment7']},
    'type2': {
        'varname2': ['type3', 'comment2'],
        'varname3': ['type3', 'comment3'],
        'varname4': ['none', 'comment4']
    },
    'type3': {'varname5': ['none', 'comment5']}
}

def get_var_paths(graph, start_type):
    result = []
    def dfs(current_type, path):
        # 获取当前类型对应的变量列表，不存在则终止
        vars_dict = graph.get(current_type)
        if not vars_dict:
            return
        for var_name, (next_type, _) in vars_dict.items():
            # 将当前变量加入路径
            path.append(var_name)
            # 如果下一个类型是none，直接保存路径
            if next_type == 'none':
                result.append(path.copy())
            else:
                # 递归遍历下一个类型
                dfs(next_type, path)
            # 回溯：移除当前变量，处理同层级其他变量
            path.pop()
    dfs(start_type, [])
    return result

# 测试
print(get_var_paths(graph, 'type1'))

输出结果与预期一致：

[
    ['varname1', 'varname2', 'varname5'],
    ['varname1', 'varname3', 'varname5'],
    ['varname1', 'varname4'],
    ['varname7']
]

2. 获取对应注释路径 #

只需修改DFS中保存的内容，把变量名换成注释即可：

def get_comment_paths(graph, start_type):
    result = []
    def dfs(current_type, path):
        vars_dict = graph.get(current_type)
        if not vars_dict:
            return
        for var_name, (next_type, comment) in vars_dict.items():
            path.append(comment)
            if next_type == 'none':
                result.append(path.copy())
            else:
                dfs(next_type, path)
            path.pop()
    dfs(start_type, [])
    return result

# 测试
print(get_comment_paths(graph, 'type1'))

输出：

[
    ['comment1', 'comment2', 'comment5'],
    ['comment1', 'comment3', 'comment5'],
    ['comment1', 'comment4'],
    ['comment7']
]

3. 通用函数（可选） #

如果需要灵活切换变量/注释，可以写一个通用函数：

def get_paths(graph, start_type, get_item):
    result = []
    def dfs(current_type, path):
        vars_dict = graph.get(current_type)
        if not vars_dict:
            return
        for var_name, (next_type, comment) in vars_dict.items():
            item = get_item(var_name, comment)
            path.append(item)
            if next_type == 'none':
                result.append(path.copy())
            else:
                dfs(next_type, path)
            path.pop()
    dfs(start_type, [])
    return result

# 获取变量路径
var_paths = get_paths(graph, 'type1', lambda v, c: v)
# 获取注释路径
comment_paths = get_paths(graph, 'type1', lambda v, c: c)

关键说明 #

• 回溯逻辑：每次递归前append当前元素，递归结束后pop，保证同层级变量的路径互不干扰
• 终止条件：遇到next_type == 'none'时直接保存当前路径，无需继续递归
• 结构适配：严格对应你的图结构，遍历变量时正确提取next_type和注释

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