;;; DFS
;;; Takes graphs in adjacency list form
;;; maintain as state:
;;; the graph,
;;; the traversal so far (in reverse order, for easy augmentation)
;;; the stack of lists of neighbors to see
;;; the current list of neighbors-to-see
;;;
;;; Using the abbreviation: neighbors-to-see = nts
(load "p84.lisp")
(defun dfs (graph node)
(dfs-aux graph (list node) nil (neighbors node graph))
)
(defun dfs-aux (graph traversal stack nts)
(cond
;; case 1: next neighbor to see has already been visited
((and nts (member (car nts) traversal))
;; just disregard this neighbor
(dfs-aux graph traversal stack (cdr nts)))
;; case 2: next neighbor to see not yet visited
(nts
;; pushd remaining list of neighbors to see, start a new one
(dfs-aux graph
(cons (car nts) traversal)
(cons (cdr nts) stack)
(neighbors (car nts) graph)))
;; case 3: no more neighbors to see, but stack not empty
(stack
;; pop a list of neighbors to see from stack
(dfs-aux graph traversal (cdr stack) (car stack)))
;; case 4: no more neighbors to see, empty stack
(t
;; return traversal; remember it is built reversed
(reverse traversal))
)
)