Clojure中的神祕無限循環

Question

我正在編寫一個Clojure函數，通過在有向圖上進行深度優先搜索來執行拓撲排序，並且對於某些輸入它不會終止。它使用循環復發，但我沒有看到任何用於參數的惰性序列來重複發生，這似乎是無限循環中最常見的罪魁禍首。我在下面的示例輸入的紙上運行該程序，他們似乎都工作正常。

(require '[clojure.set :as set]) 

;graph is a hash map, keys are nodes, vals are 
;collections of other nodes that node points to 
(defn DFSsort [graph] 
    (loop [stack `(~(ffirst graph)), 
     visited '()] 
    (let [unvisited (set/difference (set (keys graph)) 
            (set visited)), 
      node (peek stack), 
      neigh (graph node)] 
     (if (empty? stack) 
     (if (seq unvisited) 
      (recur (conj stack (first unvisited)) 
       visited) 
      visited) ; return 
     (if (seq (set/difference (set neigh) (set visited)))  
      (if (not-any? (partial = (first neigh)) stack) 
      (recur (conj stack (first neigh)) 
        visited) 
      "Cycle detected!") ; abort 
      (recur (pop stack) 
       (conj visited node))))))) 

(DFSsort {1 [2 3], 2 [3], 3 []}) 
;=> (1 2 3) 

(DFSsort {1 [2 3], 2 [], 3 []}) 
;Infinite loop 

(DFSsort {1 [2 3], 2 [], 3 [2]}) 
;Infinite loop 

Answer 1

當調用RECUR您正在使用的第一當前節點的鄰居，而不是第一個未訪問鄰居的。對於節點1，您總是將節點2添加到堆棧。

試試這個：

(defn DFSsort [graph] 
    (loop [stack `(~(ffirst graph)), 
     visited '()] 
    (println stack visited) 
    (let [unvisited (set/difference (set (keys graph)) 
            (set visited)), 
      node (peek stack), 
      neigh (graph node) 
      unseen-neigh (seq (set/difference (set neigh) (set visited)))] 
     (if (empty? stack) 
     (if (seq unvisited) 
      (recur (conj stack (first unvisited)) 
       visited) 
      visited) ; return 
     (if unseen-neigh 
      (if (not-any? (partial = (first unseen-neigh)) stack) 
      (recur (conj stack (first unseen-neigh)) 
        visited) 
      "Cycle detected!") ; abort 
      (recur (pop stack) 
       (conj visited node)))))))