Существует ли путь между двумя вершинами графа - Lisp

Узнай цену своей работы

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

Задача звучит так: "Граф задан с помощью цепных списков. Определить, существует ли путь между двумя заданными вершинами." Я граф представляю в таком виде: ((2 3) (1) (1)) - то есть, в каждом элементе списка перечисляю числа вершин, с которыми соединена вершина с порядковым номером данного элемента в списке. Мой код:
(defun find (A B L)
 (cond
   ((null L) nil)
   ((EQ A B) nil)
   (T (cond
       ((member B (nth A L)) T)
       (T (let (S A) (F A B L S)))
      )
   )
 )
)
 
(defun F (X B L S)
 (dolist (i (nth X L) 'ok)
             (cond
               ((null L) nil)
               ((member i S) nil)
               ((member B (nth i L)) T)
               (T (AND (cons i S) (F i B L S)))
             )
 )
)
По моей задумке, должен быть совершён проход по всем ответвлениям до тех пор, пока либо не найдётся вторая вершина, либо не окажется, что проверять больше нечего (сохраняю номера пройденных вершин в список S и каждый раз проверяю, не была ли уже проверена эта вершина). Проблема в том, что при попытке проверить работу программы ошибка выдаётся уже на этапе считывания аргументов:
CL-USER> (find 2 3 '((2 3) (1) (1)))
; Evaluation aborted on #<CCL::SIMPLE-PROGRAM-ERROR #x2100B89C5D>.
Incorrect keyword arguments in (((2 3) (1) (1))) . [Condition of type CCL::SIMPLE-PROGRAM-ERROR] Restarts: 0: [RETRY] Retry SLIME REPL evaluation request. 1: [*ABORT] Return to SLIME's top level. 2: [ABORT-BREAK] Reset this thread 3: [ABORT] Kill this thread Backtrace: 0: (NIL #<Unknown Arguments>) 1: (CCL::CALL-CHECK-REGS FIND 2 3 ((2 3) (1) (1))) 2: (CCL::CHEAP-EVAL (FIND 2 3 '((2 3) (1) (1)))) 3: (SWANK::EVAL-REGION "(find 2 3 '((2 3) (1) (1)))\n") Locals: STRING = "(find 2 3 '((2 3) (1) (1)))\n" STREAM = #<STRING-INPUT-STREAM #x2100B89F4D> VALUES = NIL - = (FIND 2 3 '((2 3) (1) (1))) SWANK::FORM = (FIND 2 3 '((2 3) (1) (1))) 4: ((:INTERNAL SWANK::REPL-EVAL)) 5: (SWANK::TRACK-PACKAGE #<CCL:COMPILED-LEXICAL-CLOSURE (:INTERNAL SWANK::REPL-EVAL) #x2100C1686F>) 6: (SWANK::CALL-WITH-RETRY-RESTART "Retry SLIME REPL evaluation request." #<CCL:COMPILED-LEXICAL-CLOSURE (:INTERNAL SWANK::REPL-EVAL) #x2100C168EF>) 7: (SWANK::CALL-WITH-BUFFER-SYNTAX NIL #<CCL:COMPILED-LEXICAL-CLOSURE (:INTERNAL SWANK::REPL-EVAL) #x2100C1692F>) 8: (SWANK::REPL-EVAL "(find 2 3 '((2 3) (1) (1)))\n") 9: (CCL::CALL-CHECK-REGS SWANK:LISTENER-EVAL "(find 2 3 '((2 3) (1) (1)))\n") 10: (CCL::CHEAP-EVAL (SWANK:LISTENER-EVAL "(find 2 3 '((2 3) (1) (1)))\n")) 11: (SWANK:EVAL-FOR-EMACS (SWANK:LISTENER-EVAL "(find 2 3 '((2 3) (1) (1)))\n") "COMMON-LISP-USER" 388) 12: (SWANK::PROCESS-REQUESTS NIL) 13: ((:INTERNAL SWANK::HANDLE-REQUESTS)) 14: ((:INTERNAL SWANK::HANDLE-REQUESTS)) 15: (SWANK-BACKEND:CALL-WITH-DEBUGGER-HOOK #<Compiled-function SWANK:SWANK-DEBUGGER-HOOK #x210073F1EF> #<CCL:COMPILED-LEXICAL-CLOSURE (:INTERNAL SWANK::HANDLE-REQUESTS) #x2100ADC64F>) 16: (SWANK::CALL-WITH-BINDINGS ((*STANDARD-OUTPUT* . #<SWANK-BACKEND::SLIME-OUTPUT-STREAM #x2100ADB44D>) (*STANDARD-INPUT* . #<SWANK-BACKEND::SLIME-INPUT-STREAM #x2100ADB80D>) ..))) #<CCL:COMPILED-LEXICAL.. 17: (SWANK::HANDLE-REQUESTS #<CONNECTION #x210098BEDD> NIL) 18: (CCL::RUN-PROCESS-INITIAL-FORM #<PROCESS repl-thread(10) [Active] #x2100ACA69D> (#<CCL:COMPILED-LEXICAL-CLOSURE (:INTERNAL CCL::%PROCESS-RUN-FUNCTION) #x2100ACA43F>)) 19: ((:INTERNAL (CCL::%PROCESS-PRESET-INTERNAL (CCL:PROCESS))) #<PROCESS repl-thread(10) [Active] #x2100ACA69D> (#<CCL:COMPILED-LEXICAL-CLOSURE (:INTERNAL CCL::%PROCESS-RUN-FUNCTION) #x2100ACA43F>)) 20: ((:INTERNAL CCL::THREAD-MAKE-STARTUP-FUNCTION))
Если поменять местами аргументы в коде и при вызове функции, поставив список вперёд ("L A B" - у меня было так изначально), то также вызывает ошибку третий аргумент. Подскажите, что не так и как это исправить, пожалуйста.

Решение задачи: «Существует ли путь между двумя вершинами графа»

textual
Листинг программы
(defun search (v graph chk)  ;; найти первую вершину, связанную с v и непосещенную
  (dolist (i graph nil)
    (when (and (eq v (car i)) (not (member (cadr i) chk))) (return (cadr i)))
    (when (and (eq v (cadr i)) (not (member (car i) chk))) (return (car i)))))
 
    
(defun dfs (graph chk stack)
  (let ((w (if (null stack) nil (search (car stack) graph chk))))
       (cond ((and (null w) (null stack)) nil)
             ((null w) (dfs graph chk (cdr stack)))
             (t (cons (list (car stack) w) (dfs graph (cons w chk) (cons w stack)))))))
 
(defun path-exists (graph v1 v2)
   (let ((pth (dfs graph (list v1) (list v1))))
      (member v2 (apply 'append pth))))
 
;; Проба:
 
(path-exists '((a b) (a c) (b c) (d b) (d c) (b e) (d e)) 'c 'e)
 
==> T
 
(path-exists '((a b) (a c) (b c) (d b) (d c) (f e) (g e)) 'c 'e)
 
==> NIL

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

В этом коде реализована функция поиска пути между двумя вершинами в графе с помощью алгоритма Depth-First Search (DFS). Список графовых вершин, в которых находится первая непосещенная вершина, связанная с заданной, строится с помощью рекурсивного вызова функции dfs. В этом списке вершин, в которых еще не было посещено ни одной вершины, ищется первая вершина, связанная с заданной. Если такая вершина найдена, то она добавляется в стек, и рекурсивный вызов функции dfs происходит для оставшихся вершин графа. Если такая вершина не найдена, то рекурсивный вызов функции dfs происходит для следующей вершины графа. Если список вершин графа исчерпан, а путь не найден, то возвращается значение NIL. Проба кода показывает, что путь между вершинами 'c' и 'e' в графе '((a b) (a c) (b c) (d b) (d c) (b e) (d e)) существует, а в графе '((a b) (a c) (b c) (d b) (d c) (f e) (g e)) — нет.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 4.25 из 5