На этом шаге мы приведем общие сведения по организации поиска на графах в языке LISP.
Одной из самых распространенных задач, связанных с графами, является поиск на графах.
Под поиском на графах мы будем понимать процесс систематического просмотра всех вершин графа с целью отыскания вершин, удовлетворяющих некоторому условию.
Для организации простейшего поиска в графе, заданном с помощью неизвестной (!) списочной структуры, используется инкапсулированный тип данных множество. Идея алгоритма ясна из приведенной ниже программы.
Программа.
(DEFUN WALK (LAMBDA (GRAPH)
(COND ( (NULL GRAPH) NIL )
( T (LIST-SET (ONE-RANGE GRAPH)) )
)
))
; ------------------------- ;
(DEFUN LIST-SET (LAMBDA (LST)
; Функция LIST-SET преобразует список LST в множество ;
(COND ( (NULL LST) NIL )
( (MEMBER (CAR LST) (CDR LST))
(LIST-SET (CDR LST)) )
( T (CONS (CAR LST)
(LIST-SET (CDR LST))) )
)
))
; -------------------------- ;
(DEFUN ONE-RANGE (LAMBDA (LST)
; Списочная структура LST "ужимается" в ;
; одноуровневый список ;
( (NULL LST) NIL )
( (ATOM LST) (CONS (CAR LST) NIL) )
( APPEND (ONE-RANGE (CAR LST)) (ONE-RANGE (CDR LST)) )
))
Тестовый пример:
$ (WALK '((1 . (2 3 4)) (2 . (3)) (3 . (4)))) (1 2 3 4)
На следующем шаге мы рассмотрим поиск в глубину.
