Эйлеров путь на графах - Lisp

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

Здравствуйте! Напишите, пожалуйста, программу, определяющую ~~эйлеровый~~ эйлеров путь, начинающийся с заданной вершины неориентированного графа. Путь называется эйлеровым, если проходит все ребра графа по одному разу! Если путь не существует, то программа должна возвращать NIL. Спасибо всем заранее!

Решение задачи: «Эйлеров путь на графах»

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

(defun euler (start graph)
  (let ((r nil) (d nil))
    (labels ((eu! (v g) 
               (dolist (vv g t)
                 (unless (member vv d :test #'equal)
                    (cond ((eq v (car vv)) (push vv d) (eu! (cadr vv) g))
                          ((eq v (cadr vv))(push vv d) (eu! (car vv) g)))))
               (push v r)))
             (eu! start graph) r)))
 
 
(setq *h* '((1 2) (1 3) (2 3) (2 7) (2 5) (3 4) (3 5) (4 5) (5 6) (6 7)))
 
CL-USER 7 > (euler 1  *h*)
(1 2 3 4 5 2 7 6 5 3 1)
 
CL-USER 8 > (euler 4  *h*)
(4 3 1 2 3 5 2 7 6 5 4)

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

В этом коде реализована функция euler, которая вычисляет Эйлеров цикл в графе. Граф представлен в виде списка списков, где каждый внутренний список содержит два числа, которые соответствуют вершинам графа, соединенным ребром. Функция принимает два аргумента: начальную вершину и граф. В первой строке кода определяются две пустые переменные r и d, которые будут использоваться для хранения результата. Затем следует определение внутренней функции eu!, которая будет использоваться для обхода графа. Эта функция принимает три аргумента: текущую вершину, граф и текущий список ребер. Внутри функции используется цикл dolist, который перебирает все вершины графа. Если текущая вершина не является членом текущего списка ребер, то она добавляется в список d (если это не первая встреча с этой вершиной) и вызывается рекурсивно функция eu! для следующей вершины. Если текущая вершина является первой встречей с этим ребром, то она добавляется в список d. В конце определения функции eu! добавляется текущая вершина в список r. После определения функции eu! следует вызов этой функции для начальной вершины и графа. Результатом является список, содержащий все вершины графа в порядке обхода. Затем в консоли CL-USER создается глобальная переменная *h*, которая содержит граф в виде списка списков. Наконец, вызывается функция euler с аргументами 1 и *h*, что вызывает Эйлеров цикл для графа и выводит результат. Результатом выполнения кода будет список, содержащий все вершины графа в порядке обхода. Порядок обхода определяется функцией eu!. В данном случае, если начать с вершины 1, то обход будет происходить в следующем порядке: 1, 2, 3, 4, 5, 2, 7, 6, 5, 3, 1. Если начать с вершины 4, то обход будет происходить в следующем порядке: 4, 3, 1, 2, 3, 5, 2, 7, 6, 5, 4.