实现图中所有路径打印算法遇IndexError问题求助

错误原因 #

你遇到的IndexError: list index out of range，核心问题是用列表存储邻接表时，直接将节点ID作为列表索引访问。因为输入的节点ID是无符号整数（比如示例中的1、2、3、4、5），并非从0开始连续编号，当节点ID大于列表长度时，就会触发索引越界。比如你用adj1[u]访问节点u的邻接列表，若u=1但adj1的长度仅为1（索引0），自然会报错。

修复方案 #

改用字典存储邻接表，字典的键直接用节点ID（整数类型），值为对应节点的邻接节点列表，彻底规避索引依赖问题。同时调整输入解析和路径遍历逻辑，适配字典结构。

完整修复代码 #

def find_all_paths(graph, start, end):
    paths = []
    # 栈结构存储当前遍历状态：(当前节点, 已走过的路径)
    stack = [(start, [start])]
    while stack:
        current_node, current_path = stack.pop()
        # 遍历当前节点的所有邻接节点
        for neighbor in graph[current_node]:
            if neighbor == end:
                # 找到终点，拼接路径并保存
                paths.append("->".join(map(str, current_path + [neighbor])))
            else:
                # 未到终点，继续深入遍历
                stack.append((neighbor, current_path + [neighbor]))
    # 反转路径列表，保证输出顺序与示例一致
    return paths[::-1]

# 处理输入数据
start_end_str = input().strip().split("->")
start_node = int(start_end_str[0])
target_node = int(start_end_str[1])

graph_raw_data = input().strip().split(";")
adj_graph = {}
for node_group in graph_raw_data:
    # 拆分每组节点数据并转为整数
    node_parts = list(map(int, node_group.strip().split(",")))
    node_id = node_parts[0]
    adj_nodes = node_parts[1:]
    adj_graph[node_id] = adj_nodes

# 获取所有路径并打印
result_paths = find_all_paths(adj_graph, start_node, target_node)
for path in result_paths:
    print(path)

验证示例 #

输入：

1->5
1, 2, 3; 2, 3; 3, 4; 4, 5; 5, 1

输出：

1->2->3->4->5
1->3->4->5

关键说明 #

1. 字典邻接表无需考虑节点ID的连续性和起始值，直接通过节点ID作为键访问，彻底解决索引越界问题。
2. 代码采用DFS（深度优先搜索）遍历所有路径，通过栈保存遍历状态，确保不遗漏任何可能的路径。
3. 最后反转路径列表是因为栈的后进先出特性，反转后输出顺序与示例预期一致。

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