查找带环的有向图中的所有路径

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))))))))

Answer 1

请参阅计算最短路径的通用方法，了解可以返回图中所有路径的算法（即使存在循环）作为有限时间内边字母表上的正则表达式（假设有限图）。

Answer 2

您需要将路径列表 (mark-list) 与节点一起传递，因为这是状态的一部分。我在此代码中将其重命名为 path：

(defun all-paths (start end)
  (let ((stack (list '(start (start)))) ; list of (node path) elements
        (all-path-list '()))
    (do  ()
      ((not stack))          
      (let ((item (pop stack)))
        (let ((node (first item))
              (path (second item)))
          (format t "I: ~a~%" (search-node-data node)) 
          (cond ((graph-equal node end)
                 (format t "*Q: ~a~%"
                         (loop for var in path
                               collect (search-node-data var)))))
          (loop for next in (graph-next node)
                do        
                (cond ((not (in next path :test #'graph-equal))
                       (push (list next (cons next path)) stack)))))))))