 Дан граф с циклами, построить без циклов |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
| Somebody |
 5.12.2003 4:12
Сообщение
#1
|
|
Гость  |
Помогите с этой задачей.
|
 
|
|
  |
Ответов(1 - 4)
| trminator |
5.12.2003 18:39
Сообщение
#2
|
|
Четыре квадратика  Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация:  4  |
Создаешь новый граф без дуг, но с тем же количеством вершин. Затем добавляешь одну дугу, если она не создает цикл.
Как распознать цикл: завести массив Mark[1..кол-во вершин], это будет массив "меток" вершин. 1) Сначала Mark[i] = i для всех i от 1 до кол-ва вершин 2) Выбираем новое ребро в том случае, если "метки" вершин, которые оно соединяет, разные. Пусть они равны, например, k и m. 3) Теперь нужно заменить по всему массиву все встречающиеся в нем элементы равные k, на m. Можно переходить снова к шагу 2. 4) Закончить, когда весь массив Mark будет заполнен одинаковыми элементами (подробнее, как искать циклы, можно посмотреть в книге Окулова, глава Алгоритмы на графах, раздел "Каркас минимального веса. Метод Краскала". Фактически тебе нужно построить этот каркас, но не обязательно минимального веса. Книгу можно скачать на http://pascalnet.ru) -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
   |
|
| Somebody |
9.12.2003 2:45
Сообщение
#3
|
|
Гость |
А исходника нету?
|
|
|
|
| trminator |
9.12.2003 8:36
Сообщение
#4
|
|
Четыре квадратика Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: 4 |
Кстати у тебя граф-то ориентированный? А то этот алгоритм вроде как для неориентированного... хотя может, и пройдет... Исходника нет. читай Окулова - умный мужик.
А вообще на бумажке порисуй минут 15-20-30-90, алгоритм вроде простой, написАть не должно быть очень сложно. -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
|
|
|
| trminator |
9.12.2003 8:39
Сообщение
#5
|
|
Четыре квадратика Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: 4 |
Да, для ориентированного графа это не проходит. А у тебя какой?
-------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 23.06.2025 11:33 |