如何在递归DFS函数中操作并返回字符串形式的遍历路径？

问题根源 #

1. 字符串不可变性：Python中字符串是不可变类型，output += str(starting_node)会生成新的字符串对象，递归调用时传递的是原字符串的副本，下层函数修改后的结果不会同步到上层，最终只返回初始添加的"1"。
2. 冗余的visited标记：在循环内提前标记visited[vertex] = True是多余的，因为进入dfs函数时已经执行了该操作，且可能导致逻辑混乱。
3. 路径格式缺失：原代码直接拼接节点字符串，没有添加空格，无法得到期望的带空格分隔格式。

修正方案1：递归返回拼接后的路径字符串 #

利用递归函数返回子路径，将其拼接到当前节点的字符串后，解决不可变对象的传递问题：

adj_lst = [None, [3, 4], [3], [1, 2], [1]]
size = len(adj_lst)
visited = [False] * size

def dfs(starting_node, a_lst):
    visited[starting_node] = True
    output = str(starting_node)
    for vertex in a_lst[starting_node]:
        if not visited[vertex]:
            child_path = dfs(vertex, a_lst)
            output += " " + child_path
    return output

print(dfs(1, adj_lst))  # 输出：1 3 2 4

修正方案2：使用可变列表存储路径 #

借助列表（可变对象）收集节点，最后统一格式化为字符串，更直观高效：

adj_lst = [None, [3, 4], [3], [1, 2], [1]]
size = len(adj_lst)
visited = [False] * size

def dfs(starting_node, a_lst, path):
    visited[starting_node] = True
    path.append(str(starting_node))
    for vertex in a_lst[starting_node]:
        if not visited[vertex]:
            dfs(vertex, a_lst, path)

path = []
dfs(1, adj_lst, path)
print(" ".join(path))  # 输出：1 3 2 4

内容的提问来源于stack exchange，提问作者Mosheur Rahman Wolied