IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Дан граф с циклами, построить без циклов
сообщение
Сообщение #1


Гость






Помогите с этой задачей.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


Создаешь новый граф без дуг, но с тем же количеством вершин. Затем добавляешь одну дугу, если она не создает цикл.

Как распознать цикл: завести массив Mark[1..кол-во вершин], это будет массив "меток" вершин.
1) Сначала Mark[i] = i для всех i от 1 до кол-ва вершин
2) Выбираем новое ребро в том случае, если "метки" вершин, которые оно соединяет, разные. Пусть они равны, например, k и m.
3) Теперь нужно заменить по всему массиву все встречающиеся в нем элементы равные k, на m. Можно переходить снова к шагу 2.
4) Закончить, когда весь массив Mark будет заполнен одинаковыми элементами

(подробнее, как искать циклы, можно посмотреть в книге Окулова, глава Алгоритмы на графах, раздел "Каркас минимального веса. Метод Краскала". Фактически тебе нужно построить этот каркас, но не обязательно минимального веса. Книгу можно скачать на http://pascal.net.ru)


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






А исходника нету?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


Кстати у тебя граф-то ориентированный? А то этот алгоритм вроде как для  неориентированного... хотя может, и пройдет... Исходника нет. читай Окулова - умный мужик.

А вообще на бумажке порисуй минут 15-20-30-90, алгоритм вроде простой, написАть не должно быть очень сложно.


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


Да, для ориентированного графа это не проходит. А у тебя какой?


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.09.2020 11:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name