Scheme中无向图递归DFS遍历结果异常问题排查

问题背景 #

我有一个节点编号0至5的无向图，邻接关系用向量#((1 2) (0 3) (0) (1) (5) (4))定义（节点0连接1、2，节点1连接0、3，以此类推）。我想用递归DFS算法实现图遍历，伪代码如下：

Function walk(vector: vadj, integer: x, list: acc)
If x is not in acc then
append x to acc
Foreach successor y of x
walk(vadj, y, acc)
EndForeach
EndIf
EndFunction

我用Scheme写了如下实现：

(define (walk vadj x acc)
  (unless (member x acc)
    (set! acc (append acc (list x)))
    (let loop ((lst (vector-ref vadj x)))
      (unless (null? lst)
        (walk vadj (car lst) acc)
        (loop (cdr lst))))))

(let ((adj #((1 2) (0 3) (0) (1) (5) (4)))
      (res '()))
  (walk adj 0 res)
  (newline)(display res))

运行后结果是空列表，预期结果应为'(0 1 3 2)，怀疑是acc在递归环境中被重新定义导致问题。

问题原因 #

问题出在Scheme的传值调用机制和set!的作用范围上：

• 每次调用walk时，参数acc是传入值的副本，并非引用传递。
• set! acc仅修改当前函数环境中的acc变量，不会影响外层作用域的res，也不会同步到其他递归调用的acc参数中。
• 最外层的res始终是初始的空列表'()，因此最终输出为空。

解决方案 #

方案1：纯函数式实现（推荐，符合Scheme函数式编程风格） #

让walk函数返回更新后的遍历列表，全程使用不可变数据：

(define (walk vadj x acc)
  ; 如果x已在acc中，直接返回原列表
  (if (member x acc)
      acc
      ; 将x加入acc后，递归遍历所有后继节点，逐步更新列表
      (let loop ((lst (vector-ref vadj x))
                 (new-acc (append acc (list x))))
        (if (null? lst)
            new-acc
            (loop (cdr lst) (walk vadj (car lst) new-acc))))))

(let ((adj #((1 2) (0 3) (0) (1) (5) (4))))
  (let ((res (walk adj 0 '())))
    (newline)
    (display res))) ; 输出: (0 1 3 2)

方案2：使用可变容器（盒子） #

通过box包装列表，让所有递归调用共享同一个可变容器，修改容器内的列表内容：

(define (walk vadj x acc-box)
  (unless (member x (unbox acc-box))
    ; 更新盒子内的列表
    (set-box! acc-box (append (unbox acc-box) (list x)))
    (let loop ((lst (vector-ref vadj x)))
      (unless (null? lst)
        (walk vadj (car lst) acc-box)
        (loop (cdr lst))))))

(let ((adj #((1 2) (0 3) (0) (1) (5) (4)))
      (res (box '())))
  (walk adj 0 res)
  (newline)(display (unbox res))) ; 输出: (0 1 3 2)

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