Python图DFS遍历结果存疑：我的实现返回值是否正确？

你的DFS实现本身没有逻辑错误，出现遍历顺序和预期不同的原因是DFS的遍历顺序并不唯一，它取决于邻节点的遍历顺序——而你定义图时用了set存储邻接点，Python的set是无序集合，迭代时的顺序是不确定的（不同环境或版本可能有差异）。

为什么得到[0,3,1,2,4]？ #

你代码中遍历graph['0']的邻接点时，set(['1','2','3'])的迭代顺序恰好是3→1→2，所以递归会先处理节点3（这条路径走到头后回溯），再处理节点1，接着是节点2和4，最终得到你看到的输出。

如何得到预期的[0,1,2,4,3]？ #

如果需要固定的遍历顺序，只需确保邻接点的遍历顺序是可控的。最简单的方法是在遍历前对邻接点进行排序，修改代码如下：

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
        
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        
        # 对邻接点排序，保证遍历顺序固定为升序
        for neighbour in sorted(graph[node]):
            dfs(graph, neighbour, visited=visited)

dfs(graph, '0')

运行这段代码就会输出0 1 2 4 3，和你的预期一致。

补充说明 #

• DFS的核心是优先沿着一条路径深入，直到无法继续再回溯，只要符合这个逻辑的遍历结果都是合法的，顺序本身没有“对错”之分。
• 如果不需要固定顺序，你的原代码完全没问题；如果需要稳定的遍历顺序，避免使用无序集合存储邻接点，或者在遍历时主动排序。

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