使用循环查找有向图中的所有路径

Question

我正在研究一个问题,该问题需要在有向图中找到两个节点之间的所有路径.图表可能有周期.

请注意,此特定实现方法是迭代DFS.

我考虑过的几种方法如下 -

• BFS似乎没有办法整齐地管理节点之间的这种路径关系.

• 我没有看到DFS递归算法在找到终止节点时传递路径的简单机制.(可能已经完成了,如果我实现了一个Maybe monad类的东西).

• 创建GRAPH-PARENT例程.这将在现有代码中添加大量的流失(和错误).

抽象地说,需要生成的是需要生成树,以节点为根,所有叶子都是终止节点.从叶到根的每条路径都是合法的路径.这就是递归DFS会追溯到的.

我有理由相信它可以在这里完成,但我不知道该怎么做.

我已为此算法定义了一个协议,其中可以为任意对象定义GRAPH-EQUAL和GRAPH-NEXT.

调试节点类型是SEARCH-NODE,它具有数据访问器SEARCH-NODE-DATA.

(defun all-paths (start end)
  (let ((stack (list start))
        (mark-list (list start))   ;I've chosen to hold marking information local to all-paths, instead of marking the objects themselves.
        (all-path-list '()))       ; Not used yet, using debug statements to think about the problem
    (do  ()  ;; intializing no variables
     ;; While Stack still has elements
         ((not stack))          
      (let ((item (pop stack)))
    ;; I'm looking at the item.
    (format t "I: ~a~%" (search-node-data item)) 
    (cond ((graph-equal item end)
           (format t "*Q: ~a~%" (loop for var in stack collect (search-node-data var)))
           ;;Unmark the terminal node so we can view it it next time.
           (setf mark-list (remove item mark-list))))

        (loop for next in (graph-next item)
           do        
            (cond ((not (in next mark-list :test #'graph-equal))
                    ;; mark the node
                    (push next mark-list)
                    ;;Put it on the stack
                    (push next stack))))))))