Метод поиска в ширину

;; список вершин, связанных с данной и не посещенных
 
(defun getall (v graph chk) 
 (remove-if #'(lambda (z) (member z chk))
                 (mapcar #'(lambda (y) (if (eq (car y) v) (cadr y) (car y))) 
                        (remove-if-not #'(lambda (x) (member v x)) graph))))
 
;; обход в ширину с построением каркаса                       
                        
(defun bfs! (graph &optional (chk '(1)) (queue '(1)))
   (cond ((null queue) nil)
         (t (let ((n (getall (car queue) graph chk)))
                 (append (mapcar #'(lambda (x) (list (car queue) x)) n) (bfs! graph (append chk n) (append (cdr queue) n)))))))
 
;; найти путь в каркасе от вершины n1 до n2
                 
(defun spath (carc n1 n2 &optional (c carc) (r nil))
  (cond ((null carc) (raiseerror "Неверен номер вершины"))
        ((= n1 n2) r)
        ((= (cadar carc) n2) (spath c n1 (caar carc) c (cons (car carc) r)))
        (t (spath (cdr carc) n1 n2 c r)))) 
                        
;; ведущая программа   
   
(defun  task (graph n1 n2)
  (let ((carc (bfs! graph (list n1) (list n1))))
        (spath carc n1 n2)))
        
      
(task '((1 2) (1 3) (2 4) (2 5) (3 5) (3 6) (4 5) (5 6)) 2 6)
 
==> ((2 5) (5 6))