关于DFS算法递归访问完节点后回溯父节点的疑问

问题背景 #

用户提供了DFS的Python实现代码及运行结果，对DFS的回溯逻辑存在疑问：当节点6的唯一相连节点7已被访问后，预期探索路径到1-2-7-6就结束，但实际输出有后续内容，想了解原因。

代码 #

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False]*9

def dfs(graph, v, visited):
  visited[v] = True
  #print(v, end='')
  for i in graph[v]:
    print("i:",i,"v:",v)
    if not visited[i]:
      print("no")
      dfs(graph,i,visited)

运行结果 #

i: 2 v: 1
no
i: 1 v: 2
i: 7 v: 2
no
i: 2 v: 7
i: 6 v: 7
no
i: 7 v: 6
i: 8 v: 7
no
i: 1 v: 8
i: 7 v: 8
i: 3 v: 1
no
i: 1 v: 3
i: 4 v: 3
no
i: 3 v: 4
i: 5 v: 4
no
i: 3 v: 5
i: 4 v: 5
i: 5 v: 3
i: 8 v: 1

疑问解析 #

你误解了DFS的执行逻辑——DFS不是访问到某个叶子节点就直接终止，而是会沿着递归调用栈逐层回溯，继续处理父节点中尚未遍历完的相邻节点。

我们一步步拆解代码的执行路径：

1. 从节点1开始，标记为已访问，遍历其相邻节点：
   • 第一个节点是2，未访问，打印i:2 v:1和no，递归进入节点2。
2. 节点2标记为已访问，遍历相邻节点：
   • 第一个节点是1，已访问，仅打印i:1 v:2，不进入递归。
   • 第二个节点是7，未访问，打印i:7 v:2和no，递归进入节点7。
3. 节点7标记为已访问，遍历相邻节点：
   • 第一个节点是2，已访问，打印i:2 v:7，不递归。
   • 第二个节点是6，未访问，打印i:6 v:7和no，递归进入节点6。
4. 节点6标记为已访问，遍历相邻节点：
   • 唯一节点是7，已访问，仅打印i:7 v:6，没有递归调用。此时节点6的循环执行完毕，递归返回上一层（回到节点7的循环）。
5. 回到节点7的循环，继续处理下一个相邻节点8：
   • 节点8未访问，打印i:8 v:7和no，递归进入节点8。
6. 节点8标记为已访问，遍历相邻节点：
   • 节点1已访问，打印i:1 v:8；节点7已访问，打印i:7 v:8。循环执行完毕，递归返回上一层（回到节点7的循环）。
7. 节点7的所有相邻节点处理完毕，递归返回上一层（回到节点2的循环）。
8. 节点2的所有相邻节点处理完毕，递归返回上一层（回到节点1的循环）。
9. 回到节点1的循环，继续处理下一个未访问的相邻节点3：
   • 节点3未访问，打印i:3 v:1和no，递归进入节点3。
10. 节点3标记为已访问，遍历相邻节点：
    • 节点1已访问，打印i:1 v:3；节点4未访问，打印i:4 v:3和no，递归进入节点4。
11. 节点4标记为已访问，遍历相邻节点：
    • 节点3已访问，打印i:3 v:4；节点5未访问，打印i:5 v:4和no，递归进入节点5。
12. 节点5标记为已访问，遍历相邻节点：
    • 节点3已访问，打印i:3 v:5；节点4已访问，打印i:4 v:5。循环完毕，返回节点4的循环。
13. 节点4的循环完毕，返回节点3的循环，继续处理下一个相邻节点5（已访问），打印i:5 v:3。
14. 节点3的循环完毕，返回节点1的循环，继续处理最后一个相邻节点8（已访问），打印i:8 v:1。
15. 节点1的所有相邻节点处理完毕，整个DFS执行结束。

核心逻辑就是：每个递归调用结束后，程序会回到父节点的循环中，继续处理父节点剩余的未遍历相邻节点，这就是你看到后续输出的原因——节点6处理完后，程序回溯到节点7，继续处理它的下一个邻居8，之后再逐层回溯到节点1，处理节点3和8。

内容的提问来源于stack exchange，提问作者유한정