> 1 <

Автор Сообщение

Мила

Members


Статус

3 сообщений

Где: Kazakhstan
Род занятий:
Возраст:

#2103   2010-05-20 14:08 GMT+3 часа(ов)      
Помогите!!!
Пусть граф представлен списком вершин (вершины помечены атомами) и списком ребер (каждое ребро, в свою очередь, список из двух вершин).

Необходимо написать функцию, которая, учитывая список вершин, переводит список ребер в список списков смежных вершин указанного далее вида.
Например, исходный граф задан:
1) список вершин (b c e d a f);
2) список ребер ((b c) (с с) (a d) (e d) (e a)).

Необходимая функция преобразует эту информацию в список списков смежных вершин:
((b ©) (c (b c)) (e (d a)) (d (e a)) (a (d e)) (f nil))


Есть следущая функция которую можно использовать:


Функция (nbg x p). Эта функция будет выдавать список всех соседей вершины x, не входящих в путь p.

Алгоритм:
• просматривая все ребра графа, выбираем вершины, соседние для х (если какое-то ребро не инцидентно вершине x, то в создаваемый список добавляем nil);
• удаляем из полученного списка nil и элементы, принадлежащие пути p.

(defun ngb (x p) (remove-if #'(lambda (y) (or (null y) (member y p)))
(mapcar
#'(lambda (s)
(cond
((eql x (first s)) (second s))
((eql x (second s)) (first s))
(t nil)
)
)
r)
)
)

>(setq v '(1 2 3 4 5 6))
(setq r '((1 2) (2 3) (3 1) (1 4) (4 5) (5 6) (6 1)))

> (ngb 1 r)
(2 3 4 6)

LinkFly

Members


Статус

152 сообщений

Где: Russia
Род занятий:
Возраст:

#2124   2010-05-23 22:38 GMT+3 часа(ов)      
Вообще я бы список вершин и рёбер сначала отсортировал ..
> 1 <


Онлайн :

0 пользователь(ей), 33 гость(ей) :