> 1 <
Автор | Сообщение |
Мила
3 сообщений |
#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
152 сообщений |
#2124 2010-05-23 22:38 GMT+3 часа(ов) |
Вообще я бы список вершин и рёбер сначала отсортировал ..
|
|
> 1 <