Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Список ребер в список списков смежных вершин 
:(
    Опции темы
МилаР
Дата 20.5.2010, 10:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 7.5.2010

Репутация: нет
Всего: нет



Помогите!!! 
Пусть граф представлен списком вершин (вершины помечены атомами) и списком ребер (каждое ребро, в свою очередь, список из двух вершин). 

Необходимо написать функцию, которая, учитывая список вершин,  переводит список ребер в список списков смежных вершин указанного далее вида.
Например, исходный граф задан:
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)


PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума LISP
Void
  • Пожалуйста, создавайте темы с содержательными названиями.
  • Lisp — это целое семейство языков. Всегда указывайте в теме используемый диалект (Common Lisp, Scheme и т.д.).
  • Уважаемые учащиеся, здесь всегда рады помочь Вам, но не делать за Вас вашу работу. У вас гораздо больше шансов получить помощь, если Вы приложите усилия и поделитесь с нами проблемами и результатами. В противном случае добро пожаловать в раздел Центр Помощи.
  • Получив ответ на интересующий Вас вопрос, не забудьте пометить его как решённый.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Void.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | LISP | Следующая тема »


 




[ Время генерации скрипта: 0.0360 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.