Home / Computer science / Depth-first search (DFS)
Practice implementation
A clean-room implementation 1 of DFS in Elisp:
(defun my-depth-first-graph-search (frontier neighbors goalp)
"Perform depth-first search (DFS) on a graph.
All arguments are like those for `my-graph-search', which see."
(let ((lifo (lambda (frontier paths) (nconc paths frontier))))
(my-graph-search frontier neighbors goalp lifo)))
(defalias 'my-dfs-graph-search #'my-depth-first-graph-search)
Test.
(let ((graph '((a b c d)
(b a e i)
(c a f)
(d a g l)
(e b i j)
(f c)
(g d k l)
(i b e)
(j e)
(k g)
(l d g)))
(my-graph-search-debug t))
(princ (format "Solution: %s\n"
(my-bfs-graph-search
'((a))
(lambda (path) (alist-get (car path) graph))
(lambda (path) (eq (car path) 'f))))))
Search: (a) Search: (b a) Search: (c a) Search: (d a) Search: (e b a) Search: (i b a) Search: (f c a) Solution: (f c a)
Footnotes:
1
Based on the implementation of the generic search, which see.