Lisp dfs 不返回非循环路径

Question

我正在创建一个 Lisp 程序来查找无向图中的非循环路径，并将该路径返回给用户。该路径不一定需要是最短路径。 我的完整代码如下：

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

(defun getneighbours (graph node) ;Gets neighbors of the given node.
    (if (assoc node graph)
        (cdr (assoc node graph))
        '()
    )
)

(defun acyclicpath (graph start goal) 
    (setq visited '()) ;Reset the returnpath and visited variables for the next search.
    (setq returnpath '())
    (if (dfswithpath graph start goal) ;Path found reverse path and return.
        (reverse 'returnpath)
    )
    nil
)

(defun dfswithpath (graph node goal)
    (if (equal node goal) ;Goal reached return true.
        (push node returnpath)
        t
    )

    (push node visited) ;Update visited list.

    (dolist (neighbour (getneighbours graph node)) ;Call dfs on each neighbour of node if not already visited.
        (if (not (member neighbour visited))
            (if (dfswithpath graph neighbour goal)
                (push node returnpath)
                t
            )
        )
    )
    nil ;No path found
)

(print (acyclicpath graph 'A 'C))

运行此代码会导致 dfswithpath 函数始终返回 nil 值。我已将问题范围缩小到 dolist 函数中的递归 dfswithpath 调用。看起来它永远不会解析为 t，因此嵌套的推送函数永远不会被调用。但是，我不明白为什么会这样。

Answer 1

dfswithpath

函数返回nil，因为该函数中的最后一个形式是

nil

。要从函数返回而不是通过执行到最后一个函数，您必须使用

(return-from dfswithpath <value>)

。

（从风格上来说，只有当没有很好的方法以函数式风格编写函数时才应该使用它。）