|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
||||||||||||||||
Поиск минимального остовного дерева на графе10.08.2014, 15:22. Показов 27324. Ответов 27
Метки нет (Все метки)
Переделал программу найденную в интернете, написал через функцию.
Макс вес ребра: 5 Кол-во вершин: 2 матрица смежности: 0 1 1 0 И любое название файла, выводит: Файл создан. 1 --> 0(все верное, кроме этого нуля) Мин стоимость: 1 при вводе большего количества ребер или значения первого элемента не равным нулю, программа доходит до вывода надписи "Файл создан", а дальше останавливается... Не пойму в чем проблема... Добавлено через 26 минут Простите, остОвного дерева. Добавлено через 2 часа 15 минут убрал цикл while. Осталась проблема что после "1 --> ..." всегда выводятся нули. Добавлено через 11 часов 25 минут Немного изменил алгоритм функции, на
ругается на строчку
0
|
||||||||||||||||
| 10.08.2014, 15:22 | |
|
Ответы с готовыми решениями:
27
Поиск минимального остовного дерева на графе Визуализация построения минимального остовного дерева Поиск минимального остовного дерева в несвязном графе. Алгоритм Прима-Краскала |
|
Модератор
13773 / 10966 / 6491
Регистрация: 18.12.2011
Сообщений: 29,243
|
||
| 10.08.2014, 15:31 | ||
|
У Вас везде считается, что индексы массива в диапазоне [1:kolVer]
например:
0
|
||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
|||||||||||||||||||||
| 10.08.2014, 15:52 [ТС] | |||||||||||||||||||||
|
zss, проблема не в этом, переделал все циклы на циклы вида:
ошибка не исчезла. вот код программы, которую я нашел в интернете и переделал, она работает :
0
|
|||||||||||||||||||||
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||||
| 10.08.2014, 16:27 | ||||
|
0
|
||||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
|||||||
| 10.08.2014, 17:34 [ТС] | |||||||
|
И да, мечусь, пробую все варианты, может и заработает. Поиск минимального остовного дерева, алгоритм Прима. В алгоритме я уже давно разобрался. С реализацией возникли проблемы, вот и прибег к готовому решению. Только вот проблема, я вполне понимаю как оно работает, но не могу понять, почему не работает у меня. Сейчас еще нашел ошибку у себя. вот переделанная фунуция:
Ошибка пропала, но теперь проблема в том, что переменная rebro[iRebra] выводиться всегда равная нулю. и minCost увеличивается на min только один раз. пример вывода: 99 3 8 7 6 5 4 3 2 1 0 выводит : 1 -> 0 -> 0 Мин стоимость: 6 а должен выводить: 1 -> 3 -> 2 Мин стоимость: 7 ps. В 19 строчке вывожу переменную rebro, выводит ноль. Почему то не присваивается ей значение j2; (ну или присваивается только один раз, когда j2 и есть равное 0)
0
|
|||||||
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|||||||
| 10.08.2014, 17:46 | |||||||
0
|
|||||||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
||
| 10.08.2014, 18:02 [ТС] | ||
|
сравниваем элемент массива с минимальным(в первом случае минимальный у нас равен максимальному), если cost[i][j]<min, то проверяем переменную used на не ложь(в первом случае она правда), а далее как раз и присваиваем значение cost[i][j] переменной min.
0
|
||
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||
| 10.08.2014, 18:12 | ||
|
перевести с языка программирования на русский я и сам могу. я просил написать в чем СМЫСЛ данной строки. подсказки: 1. не элемент массива, а элемент матрицы 2. элемент матрицы - это элемент матрицы смежности, которой представлен граф 3. наводящий вопрос: когда мы пробегаемся по матрице смежности, что мы должны проверить в первую очередь?
0
|
||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
||
| 10.08.2014, 18:23 [ТС] | ||
|
В которой каждая строка отвечает за определенную вершину. например: 0 2 3 1 2 0 4 0 3 4 0 0 1 0 0 0 здесь вершина 1 связана со второй ребром размером 2, с третьей размером в три, с четвертой размером в 1. вторая вершина с первой ребром размером 2, с третьей размером 4, с четвертой не связана.. и так далее... а проверить мы должны в первую очередь, использовалась ли эта вершина ранее, если да, то игнорировать эту строку и столбец.
0
|
||
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|||
| 10.08.2014, 18:29 | |||
|
0
|
|||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
|
| 10.08.2014, 18:37 [ТС] | |
|
0
|
|
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||
| 10.08.2014, 18:42 | ||
|
правильный ответ (пишу с сожалением): а первым делом надо убедиться что есть ребро из вершины i в вершину j, что в программе и делается с помощью инструкции cost[i][j]<min, где в min лежит некоторое сигнальное значение, означающее, что нет ребра в ячейке. в строках 97-98 это четко написано. теперь надеюсь ясно почему min нельзя менять
0
|
||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
||
| 10.08.2014, 18:56 [ТС] | ||
|
первая строка матрицы: 6 5 2 8 в начале функции мы min присвоили максимальное значение ребра, пусть 99. далее мы сравниваем min c 6. Поскольку 99>6 мы присваиваем min=6; далее сравниваем 6 с 5, присваиваем min значение 5. далее аналогично 5 с 2, после чего min=2. поскольку 8>2 то min так и остается равным 2. Это означает что из первой вершины, у нас ближайший путь в вершину 3. И путь этот равен 2. А вот дальше уже, мы снова должны присвоить min=maxCost. (чего кстати у меня нет, спасибо) и идти уже по третьей строке, игнорируя 1 столбец. и так же искать минимальное значение.
0
|
||
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||
| 10.08.2014, 19:09 | ||
|
0
|
||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
|||||||||
| 10.08.2014, 19:19 [ТС] | |||||||||
|
вот на чем я сейчас остановился:
и выводит минимальную стоимость неверную...проблема с min или c minCost=minCost+min. а возможно проблема с переменной used[], и тем за что она отвечает. Как я и писал выше, проверяем первую строку, переходим на другую(куда ближе) а далее игнорируем первую строку, used[] как раз за это и отвечает...
0
|
|||||||||
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||
| 10.08.2014, 19:30 | ||
|
начинаем всё заново (по последней версии функции): строка 6: мы договорились, что это проверка на наличие ребра i->j или как?
0
|
||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
|||||||
| 10.08.2014, 19:38 [ТС] | |||||||
|
а наличие ребра у меня проверяется до этого, это здесь не имеет значения.
0
|
|||||||
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||
| 10.08.2014, 19:46 | ||
|
можете своими словами, "на пальцах" так сказать, объяснить как работает алгоритм Прима?
0
|
||
|
2 / 2 / 0
Регистрация: 10.07.2014
Сообщений: 25
|
||
| 10.08.2014, 20:19 [ТС] | ||
|
0
|
||
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
||
| 10.08.2014, 20:40 | ||
|
каковы дальнейшие действия? т.е. по какой строке матрицы ты хочешь пройтись, чтобы выбрать из этих кандидатов вершину с наименьшей стоимостью ребра?
0
|
||
| 10.08.2014, 20:40 | |
|
Помогаю со студенческими работами здесь
20
Программа для поиска минимального остовного дерева Нахождения минимального остовного дерева. Алгоритм Краскала Построение минимального остовного дерева. Использовать алгоритм Борувки Реализация алгоритма построения минимального остовного дерева для графа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Символьное дифференцирование
igorrr37 13.02.2026
/ *
Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет
значение производной при заданном х
Логарифм записывается как: (x-2)log(x^2+2) -. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога
Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
|
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
|