Форум программистов, компьютерный форум, киберфорум
Lisp
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
7 / 7 / 0
Регистрация: 17.06.2013
Сообщений: 34
1

Является ли граф циклическим

31.10.2013, 01:44. Показов 2543. Ответов 13
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Маршрут на графе определяется списком
Lisp
1
((a b) (c e) (e d) (d c) (c b) (b a) (a d))
где (a b c d e) - вершины графа. Определить, является ли он циклическим.
Пользовался поиском по форуму - не нашел такого. Помогите, если не сложно.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.10.2013, 01:44
Ответы с готовыми решениями:

Проверить , является ли граф связным
Доброго времени суток. В очередной раз без Вашей помощи не обойтись!!!!!! ЗАДАНИЕ: Дан...

Определить, является ли направленный граф ациклическим
Ориентированный граф задан с помощью цепных списков. Определить, является ли он ациклическим....

Доказать, что граф не является Эйлеровым
Подскажите решение. Задание: Дано граф: ((a b) (b e) (e d) (d a) (c a) (c b) (c d) (c e))....

Является ли первая строка циклическим сдвигом второй строки
Привет всем. Помогите пожалуйста написать код: нужно проверить, есть ли первая строка (с...

13
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
31.10.2013, 10:47 2
Определить, является ли направленный граф ациклическим
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
36601 / 20330 / 4220
Регистрация: 12.02.2012
Сообщений: 33,639
Записей в блоге: 13
31.10.2013, 12:27 3
Цитата Сообщение от rowest Посмотреть сообщение
Маршрут на графе определяется списком
- странно он как-то определен... У тебя там не опечатка? Должно быть ((a b) (b e) (e d) (d c) (c b) (b a) (a d)), мне кажется.

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun is-cycle (path)
  (let ((s (cons (caar path) nil)))
    (dolist (i path nil)
      (if (member (cadr i) s) (return t) (push (cadr i) s)))))
 
==> is-cycle
 
(is-cycle '((a b) (b e) (e d) (d c) (c b) (b a) (a d)))
 
==> T
 
(is-cycle '((a b) (b e) (e d)))
 
==> NIL
2
7 / 7 / 0
Регистрация: 17.06.2013
Сообщений: 34
31.10.2013, 21:41  [ТС] 4
Nameless One, спасибо, смотрел-смотрел да недосмотрел...

Catstail, ваше решение мне больше по душе, большое спасибо за помощь. Вот только с запуском возникли проблемы. Я до этого пользовался java-решением для лиспа, называется JATHA, там ограничен функционал, но зато запускается на чем угодно (не нужны права администратора).
Так вот этот код написан под HomeLisp, я ведь не ошибаюсь?) Установил его, потестил с простыми примерами - всё работает. А вот в вашем коде мне показало ошибку, буду признателен, если поможете её исправить
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defun is-cycle (path)
  (let ((s (cons (caar path) nil)))
    (dolist (i path nil)
      (if (member (cadr i) s) (return t) (push (cadr i) s))
    )
  )
)
 
 
==> is-cycle
(is-cycle '((a b) (b e) (e d) (d c) (c b) (b a) (a d)))
 
 
Внутри LET: RETURN: Вызов вне PROG/LOOP
==> ERRSTATE
Добавлено через 5 минут
Ага, вот нашел ваш пост о том, что проблема может быть в устаревшей библиотеке. Поищу новее) Если заработает - отпишусь
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
36601 / 20330 / 4220
Регистрация: 12.02.2012
Сообщений: 33,639
Записей в блоге: 13
31.10.2013, 21:56 5
Можно и в lispWorks запустить. Тоже будет работать.
0
7 / 7 / 0
Регистрация: 17.06.2013
Сообщений: 34
31.10.2013, 22:28  [ТС] 6
Catstail, спасибо, в lispWorks действительно работает. А с HomeLisp не удалось разобраться в чем проблема. Еще раз благодарю.

Тему можно закрывать, решение найдено =)
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
36601 / 20330 / 4220
Регистрация: 12.02.2012
Сообщений: 33,639
Записей в блоге: 13
31.10.2013, 22:33 7
Цитата Сообщение от rowest Посмотреть сообщение
А с HomeLisp не удалось разобраться в чем проблема.
- в старой версии...
0
7 / 7 / 0
Регистрация: 17.06.2013
Сообщений: 34
31.10.2013, 22:37  [ТС] 8
Catstail, Скачивал с вашего сайта, там версия HomeLisp 1.13.4, новее не находил
0
3 / 3 / 0
Регистрация: 27.10.2013
Сообщений: 35
01.11.2013, 20:59 9
Задачи о списках и графах

вот полистай этот пост, там есть решение проблемы. Там качаешь файлики прикрепленные, читаешь что надо сделать и собственно это решает проблему.
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
36601 / 20330 / 4220
Регистрация: 12.02.2012
Сообщений: 33,639
Записей в блоге: 13
01.11.2013, 21:20 10
Runes, спасибо! А то я пытался найти нить, и потерялся...
0
3 / 3 / 0
Регистрация: 27.10.2013
Сообщений: 35
01.11.2013, 23:32 11
Catstail, тоже сталкивался с этой проблемой и вот наткнулся на пост по ссылке выше)
это Вам спасибо за помощь)
0
7 / 7 / 0
Регистрация: 17.06.2013
Сообщений: 34
03.11.2013, 20:50  [ТС] 12
Catstail, подскажите, пожалуйста, правильно ли я понимаю логику работы этого кода?
Мы создаем локальную переменную, в которой объеденяем голову подсписка с основным списком, а после этого циклически проходим по каждому элементу списка и проверяем, не является ли текущий элемент списка (на котором сейчас стоим в dolist) членом того списка, что получили и записали в локальную переменную. Если это так, то возвращем true и список у нас циклический. Если же нет, то записываем этот текущий элемент в качестве головы списка из локальной переменной и переходим к следующей итерации.

Я правильно понял, что в таком случае мы проверяем условие цикличности только для первой вершины (правильно ли это вообще, потому что в циклическом графе можно из любой вершины в любую попасть?)
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
36601 / 20330 / 4220
Регистрация: 12.02.2012
Сообщений: 33,639
Записей в блоге: 13
03.11.2013, 20:57 13
Lisp
1
2
3
4
5
6
7
8
(defun is-cycle (path)
  (let ((s (cons (caar path) nil)))  ;; s будет хранить список вершин, через которые проходит путь. 
                                             ;; начинаем с первой
    (dolist (i path nil) ;; цикл по ребрам пути. i - очередное ребро
      (if (member (cadr i) s) (return t) (push (cadr i) s))))) ;; если вторая вершина ребра входит в s - обнаружен цикл
                                                                              ;; иначе добавим вторую вершину в список s
 
   ;; если dolist завершился исчерпанием списка - значит циклов нет (nil)
Мы останавливаемся на первом же цикле.

Добавлено через 1 минуту
Цитата Сообщение от rowest Посмотреть сообщение
потому что в циклическом графе можно из любой вершины в любую попасть?
- в связном неориентированном графе можно найти путь из любой вершины в любую.
1
7 / 7 / 0
Регистрация: 17.06.2013
Сообщений: 34
03.11.2013, 21:05  [ТС] 14
Я на листочке расписал, получается непонятное что-то..))

Добавлено через 1 минуту
Вот, с комментариями стало понятнее. Я неправильно понял логику работы
Цитата Сообщение от Catstail Посмотреть сообщение
(let ((s (cons (caar path) nil)))
Теперь стало ясно. Благодарю за комментарии
0
03.11.2013, 21:05
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.11.2013, 21:05
Помогаю со студенческими работами здесь

Определить, является ли одна последовательность циклическим сдвигом другой
Задано число N и две последовательности целых чисел длины N. Определить, является ли одна...

Проверить, является ли строка s циклическим сдвигом строки t (или наоборот)
Привет! Изучаю алгоритмы по книжке Седжвика. Столкнулся с вот такой задачей картинка. Проблема в...

Является ли граф ациклическим
Можно ли это реализовать с помощью path :: Graph -> Vertex -> Vertex -> Bool path g v w =...

Является ли граф связным
В задаче нужно определить является ли неориентированный граф связным. Нужно использовать стек....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru