Breadth First Search

bfs.clj

(def mygraph {:A {:B 85, :C 217, :E 173},
              :B {:F 80},
              :C {:G 186 :H 103},
              :D {},
              :E {:J 502},
              :F {:I 250}
              :G {},
              :H {:D 183 :J 167}
              :I {:J 84},
              :J {}
              })

(defn bfs [G s]
  (defstruct node-info :color :distance :parent)
  (def node-info-map (ref (reduce #(assoc %1 %2 (struct node-info "white" Integer/MAX_VALUE nil)) {} (keys G))))
  (def Q (ref (conj clojure.lang.PersistentQueue/EMPTY s)))
  (dosync (alter node-info-map assoc s (struct node-info "grey" 0 nil)))
  (loop []
    (when-not (empty? @Q)
      (let [u (peek @Q)
            adj (keys (G u))
            du (get-in @node-info-map [u :distance])]
        (dosync
         (alter Q pop)
         (doseq [v adj]
           (if (= (get-in @node-info-map [v :color]) "white")
             (do
               (alter node-info-map assoc v (struct node-info "grey" (+ du 1) u))
               (alter Q conj v))))
         (alter node-info-map assoc-in [u :color] "black"))
        (recur)))) @node-info-map)

(prn (bfs mygraph :C))