查找有循環的有向圖中的所有路徑

我正在研究需要查找有向圖中兩個節點之間的所有路徑的問題。圖表可能有周期。查找有循環的有向圖中的所有路徑

請注意，此特定實施方法是迭代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))))))))

來源

2011-09-07 Paul Nathan

一種算法可以返回在圖（即使存在循環）如以上在有限時間內的邊緣的字母表的正則表達式的所有路徑（假定一個有限圖）看A Very General Method for Computing Shortest Paths。

來源

2011-09-07 03:21:02

嗯。這是一篇極爲緻密的論文。由於將算法提取到Lisp的複雜性以及將現有代碼與代表性進行接口的要求，我不願意嘗試使用它。 –

簡短版本是「使用Floyd的算法」。本文的主要內容是Floyd的算法在一個非常普遍的數學結構 - 一個*模仿 - 上展示了所述算法在各種*模式中的使用。 –

我會短語如下。將您的圖形看作一個DFA，初始狀態顯示您的起始節點和最終狀態，顯示您的結尾節點，併爲您的所有邊緣指定唯一標籤，並將該組標籤用作字母表。此DFA接受的語言表示從您的開始節點到末端節點的所有路徑的集合。如果需要，可以使用McNaughton-Yamada算法計算該語言的正則表達式。 –

-1

您需要將路徑列表（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)))))))))

來源

2011-09-07 06:12:19

你的修改不起作用，fyi。堆棧被錯誤初始化。 –

查找有循環的有向圖中的所有路徑

回答

相關問題