DFS路径查找代码问题求助：字符串与整数节点类型不匹配

问题描述 #

我正在完成学校的顶点间路径查找作业，需要用深度优先搜索（DFS）实现两顶点间的路径查找。现有代码接近完成，但存在问题：find_path函数循环中判断节点是否在路径里时，节点是字符串类型，而路径中的start是整数类型，无法正确比较，导致重复添加节点，当前运行输出为None。期望输出应为1->2->3->4->5。

输入输出示例 #

输入 #

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

期望输出 #

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

原错误代码 #

import sys
from typing import List

stack: []

def output():
    '''
    Will print the path stored in the `stack` global variable.
    You are free to modify it to be a parameter.
    '''
    for id in stack[:-1]:
        print(f'{id}->', end='')
    try:
        print(f'{stack[-1]}')
    except IndexError:
        pass


def find_path(graph, start, target, path):
    print(start, target)
    path = path + [start]
    print(path)
    if start == target:
        return path
    for node in graph:
        print(node)
        if node not in path: ##idk what to do here..
            new_path = find_path(graph, node, target, path)
            if new_path:
                return new_path


def add_value(dict_obj, key, value):
    if key not in dict_obj:
        dict_obj[key] = list()
    dict_obj[key].append(value)


if __name__ == '__main__':
    '''
    Fetch starting and target nodes.
    '''
    start, target = [int(x) for x in input().split('->')]
    #print(start, target)
    '''
    Fetch `;` separated twitter data. <id-1: u_int>, <following: u_int>, ..<following: u_int>; ... 
    i.e: 1, 2; 2, 3; 3, 4; 4, 5; 5,
    '''
    data = input()
    data_l: List = data.split(';')
    graph = dict()
    for d in data_l:
        id, followers = d.split(', ', 1)
        # print(followers)
        following_l: List = followers.split(', ')
        for f in following_l:
            if f == '':
                # node is not following other nodes.
                continue
        add_value(graph, id, followers)
    print(graph)
    find_path(graph, start, target, [])

sys.stdout.write(output())

问题分析与修复 #

原代码存在四个核心问题：

1. 类型不匹配：主函数中start/target被转为整数，但图的键是字符串，导致判断条件失效；
2. 图构建错误：未正确拆分邻接节点，直接将整串followers存入图结构；
3. DFS逻辑错误：遍历所有节点而非当前节点的邻接节点，路径查找逻辑完全偏离；
4. 输出逻辑错误：未将查找结果传递给输出函数，且输出函数的实现不符合打印需求。

修复后的代码 #

import sys
from typing import List

def output(path):
    '''根据路径生成输出字符串'''
    if not path:
        return ""
    return '->'.join(map(str, path))

def find_path(graph, start, target, path):
    path = path + [start]
    if start == target:
        return path
    # 遍历当前节点的邻接节点
    for neighbor in graph.get(str(start), []):
        neighbor_int = int(neighbor)
        if neighbor_int not in path:
            new_path = find_path(graph, neighbor_int, target, path)
            if new_path:
                return new_path
    return None

def add_value(dict_obj, key, value):
    if key not in dict_obj:
        dict_obj[key] = list()
    dict_obj[key].append(value)

if __name__ == '__main__':
    # 获取起始和目标节点，保留整数类型后续转换
    start, target = [int(x) for x in input().split('->')]
    
    # 构建图
    data = input()
    data_l: List = data.split(';')
    graph = dict()
    for d in data_l:
        parts = d.strip().split(', ', 1)
        if len(parts) < 2:
            continue
        id_str, followers_str = parts
        following_l: List = followers_str.split(', ')
        for f in following_l:
            f = f.strip()
            if f == '':
                continue
            add_value(graph, id_str, f)
    
    # 查找路径并输出
    result_path = find_path(graph, start, target, [])
    if result_path:
        print(output(result_path))
    else:
        print("No path found")

修复点说明 #

• 类型统一：在find_path中将图中的字符串节点转为整数，与start/target类型保持一致，确保比较逻辑有效；
• 正确构建图：拆分followers为单个节点，逐个添加到对应节点的邻接列表，保证图结构符合需求；
• DFS逻辑修正：遍历当前节点的邻接节点，符合DFS路径查找的核心逻辑；
• 输出逻辑优化：修改output函数接收路径参数并返回拼接后的字符串，直接打印结果路径，避免全局变量的冗余使用。

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