0

我正在编写一个 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
4

1 回答 1

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)))))))
于 2013-02-16T11:41:47.900 回答