Существует ли путь между двумя вершинами графа - Lisp
Формулировка задачи:
(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))) ) ) )
CL-USER> (find 2 3 '((2 3) (1) (1))) ; Evaluation aborted on #<CCL::SIMPLE-PROGRAM-ERROR #x2100B89C5D>.
Решение задачи: «Существует ли путь между двумя вершинами графа»
(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)) — нет.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д