Lisp实现无环路径DFS函数始终返回nil的问题求助

你的代码存在几处语法和逻辑错误，导致dfswithpath始终返回nil，无法正确构建路径：

1. if语句逻辑颠倒 #

在dfswithpath的目标判断部分，Lisp的if语法是(if 条件 真值表达式 假值表达式)，你写的代码逻辑完全反了：

(if (equal node goal)
    (push node returnpath)
    t
)

这里找到目标节点时只执行push却不返回t，反而在没找到目标时返回t，导致后续逻辑完全混乱。

2. dolist递归无终止返回 #

dolist默认返回nil，你的代码里即便递归调用dfswithpath找到了路径，也没有让当前函数立即返回t，而是继续遍历其他邻居，最后走到函数末尾固定返回的nil。

3. reverse参数错误 #

acyclicpath里的(reverse 'returnpath)是对符号returnpath取反，而非变量returnpath的实际值，必须去掉引号。

4. 函数返回值逻辑错误 #

dfswithpath最后固定返回nil，不管是否找到路径，上层调用永远会判定为无路径。

修复后的完整代码 #

(defvar graph '((A B C)
                (B A C)
                (C A B D)
                (D C)))

(defun getneighbours (graph node) ; 获取节点的邻居列表
  (if (assoc node graph)
      (cdr (assoc node graph))
      '()))

(defun acyclicpath (graph start goal) 
  (let ((visited '())   ; 用局部变量替代全局变量，避免状态污染
        (returnpath '()))
    (if (dfswithpath graph start goal visited returnpath)
        (reverse returnpath)
        nil)))

(defun dfswithpath (graph node goal visited returnpath)
  (cond
    ((equal node goal)  ; 找到目标，加入路径并返回t
     (push node returnpath)
     t)
    ((member node visited) nil)  ; 已访问过该节点，直接返回nil
    (t
     (push node visited)
     (dolist (neighbour (getneighbours graph node) nil)
       (when (dfswithpath graph neighbour goal visited returnpath)
         (push node returnpath)
         (return t))))))  ; 找到路径后立即终止遍历并返回t

(print (acyclicpath graph 'A 'C)) ; 输出结果为 (A C) 或 (A B C)，取决于遍历顺序

额外优化说明 #

• 将visited和returnpath改为局部变量并通过参数传递，避免全局变量导致的多次调用状态残留问题。
• 用cond替代嵌套if，让逻辑结构更清晰。
• 在dolist中使用(return t)，找到路径后立即终止遍历，提升执行效率。

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