來自鄰接圖的樹

我試圖做一個從窗體{node [children]}的鄰接列表構建樹的函數。來自鄰接圖的樹

(def adjacency 
    {nil [:a] 
    :a [:b :c] 
    :b [:d :e] 
    :c [:f]})

這將導致

{nil {:a {:b {:d nil 
       :e nil} 
      :c {:f nil}}}}

不過，我試過，我不能得到它的工作。遞歸是我的一個弱點，我發現的大多數遞歸示例只處理列表上的遞歸，而不是樹。

編輯：由於在發佈時沒有編輯器和原始來源，原始數據集和結果無意間嵌套得太深。對於那個很抱歉。

來源

2013-01-19 NielsK

adjacency的每個子圖中只有一個條目。這是必要的嗎？並在結果tree相同的問題。

我希望它會更清楚：

(def adjacency {:a [:b :c] 
       :b [:d :e] 
       :c [:f]})

所以，解決辦法是：

(defn tree [m root] 
    (letfn [(tree* [l] 
      (if (contains? m l) 
       {l (into {} (map tree* (m l)))} 
       [l nil]))] 
    (tree* root)))

測試：

(tree adjacency :a) 
=> {:a {:b {:d nil 
      :e nil} 
     :c {:f nil}}}

更新。如果您不需要結果樹作爲嵌套地圖

(defn tree [m root] 
    (letfn [(tree* [l] 
      (if (contains? m l) 
       (list l (map tree* (m l))) 
       (list l nil)))] 
    (tree* root))) 

(tree adjacency :a) 
=> (:a ((:b ((:d nil) 
      (:e nil))) 
     (:c ((:f nil)))))

來源

2013-01-20 07:15:24 mobyte

我通常喜歡與樹打交道時使用clojure.walk。我假設根節點首先在adjacency向量中。

(use 'clojure.walk) 

(def adjacency 
    [{nil [:a]} 
    {:a [:b :c]} 
    {:b [:d :e]} 
    {:c [:f]}]) 

(prewalk 
(fn [x] 
    (if (vector? x) 
    (let [[k v] x lookup (into {} adjacency)] 
     [k (into {} (map (fn [kk] [kk (lookup kk)]) v))]) 
    x)) 
(first adjacency))

結果：{nil {:a {:b {:d {}, :e {}}, :c {:f {}}}}}

注：空兒都表示爲{}，而不是nil，也是子元素的地圖，而不是矢量地圖，使易於瀏覽這棵樹呢。

來源

2013-01-20 09:57:45 Ankur

來自鄰接圖的樹

回答

相關問題