Гамильтонов цикл - Lisp

Формулировка задачи:

Здравствуйте, есть такое задание: Определить функцию, на вход которой подается граф в виде ((a b) (b c) (c d)) a - начало дуги, b - конец. Функция должна определять, является ли он гамильтоновым, и если да, то найти гамильтонов цикл. Цикл в графе называется гамильтоновым, если он содержит все вершины графа ровно по одному разу. Нужна помощь, заранее спасибо.

Решение задачи: «Гамильтонов цикл»

Листинг программы

(defun is-bound (v1 v2 graph) 
  (cond ((null graph) nil)
        ((or (equal (list v1 v2) (car graph)) (equal (list v2 v1) (car graph))) t)
        (t (is-bound v1 v2 (cdr graph)))))
 
(defun setof (lst) 
  (if (null lst) nil (cons (car lst) (setof (remove (car lst) (cdr lst))))))      
        
(defun vlist (graph)
  (setof (apply 'append graph)))  
 
(defun backtrack (n vlst pth g)
  (cond  ((null pth) nil)
         ((and (is-bound (car pth) (car (last pth)) g) (= (length pth) n))
           (princ pth) (terpri))
         (t  (dolist (v vlst t)
               (when (and (not (member v pth)) (is-bound v (car pth) g))
                     (backtrack n vlst (cons v pth) g))))))
 
(defun hamilt (graph)
  (let* ((vlst (vlist graph))
         (n (length vlst)))
   (backtrack n vlst (list (car vlst)) graph)))
                     
(hamilt '((1 2) (1 3) (1 4) (1 5) (2 3) (3 4) (4 5)))
 
(5 4 3 2 1)
(2 3 4 5 1)
==> T
 
(hamilt '((1 2) (2 3) (3 4) (4 1)))
 
(1 4 3 2)
(3 4 1 2)
==> T

Объяснение кода листинга программы

В этом коде реализован алгоритм поиска Гамильтонова цикла в графе с помощью рекурсивного спуска. Он состоит из нескольких функций:

is-bound — проверяет, является ли пара вершин элементом графа.
setof — рекурсивно удаляет элемент из списка и добавляет его в начало нового списка.
vlist — рекурсивно собирает список вершин графа.
backtrack — рекурсивно ищет путь в графе от начальной вершины до конечной, помечая проходящие через неё вершины.
hamilt — ищет Гамильтонов цикл в графе. При вызове функции hamilt с графом в виде списка пар вершин, она возвращает список вершин, образующих Гамильтонов цикл, если он существует. В противном случае возвращает nil. Например, для графа ((1 2) (2 3) (3 4) (4 1)) функция hamilt вернёт список (1 4 3 2), что означает, что цикл образуют вершины 1, 4, 3 и 2.