Форум программистов, компьютерный форум, киберфорум
Наши страницы

Поиск минимального остовного дерева на графе - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Не компилируются проекты: Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped http://www.cyberforum.ru/cpp-beginners/thread1240571.html
Здравствуйте, уважаемые специалисты. Недавно начал изучать С++ Компилятор Visual C++ при попытке скомпилировать любой код выдаёт это: ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0...
C++ Конструктор копирования, аварийное завершение на этапе исполнения #include <iostream.h> #include <string.h> class String{ private: char *data; int max_length; public: String() { http://www.cyberforum.ru/cpp-beginners/thread1240568.html
C++ Будут ли все константы гарантированно инициализированы к моменту обращения к ним из разных единиц трансляции
Безопасно ли такое использование: // config.cpp const int ival = 6; const SomeNonTrivialClass obj(...); // config.h extern const int ival; extern const SomeNonTrivialClass obj; //...
Как реализовать свой тип данных C++
Здравсвтуйте,подскажите пожалуйста как реализовать с с++ свой тип данных. Допустим хочу завести массив,где каждому arr будет соответсвовать две переменные(arr.a,arr.b). Если точнее - arr.a,arr.b ......
C++ Перегруженный operator<< http://www.cyberforum.ru/cpp-beginners/thread1240484.html
Есть допустим такая дружественная функция: объявление template<typename Type> friend std::ostream& operator<<(std::ostream&, Stack<Type>&); определение template<typename Type> std::ostream&...
C++ Вывести на экран суммарный результат, указав число студентов сдавших и проваливших экзамен День добрый помогите решить задачу: есть 10 студентов ( 10 раз на екран должно высвечиватся"Введите результат" результат- если пользователь пишет 1,значит студент сдал,если пишет 2 - провалил... подробнее

Показать сообщение отдельно
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
10.08.2014, 21:42
Цитата Сообщение от frEEze00 Посмотреть сообщение
и да, программа которую я нашел в интернете(скидывал сюда ранее) работает... вот в ней я и разбираюсь.
та, которая в 3-м сообщении что-ли?
работает? щас прям. вот попробуй с этой матрицей:
C++
1
2
3
4
5
6
5
0 5 2 0 0
5 0 0 3 0
2 0 0 0 8
0 3 0 0 1
0 0 8 1 0
у меня выводит следующее:
C++
1
2
1 -> 3 -> 2 -> 4 -> 5
 Минимальная стоимость 11
нет там ребра 3->2. нифига она не работает.

Цитата Сообщение от frEEze00 Посмотреть сообщение
по той, которую еще не использовал, за использование отвечает used[].
вот тут у тебя проблемы с пониманием алгоритма. правильный ответ: ни по какой. Кандидаты на добавление в MST на следующем шаге могут быть смежными с любой вершиной, уже находящейся в MST, а пробегаясь по строке мы сможем перебрать вершины, смежные только с этой вершиной.

итак, алгоритм Прима: перед очередным шагом алгоритма несколько вершин уже находятся в MST. на этом шаге проверяются все вершины, смежные с вершинами в MST, и выбирается наименьшая, которая и добавляется в MST на этом шаге. если смежных вершин не осталось, то алгоритм завершается. вот и весь алгоритм. ах да, перед первым шагом надо добавить в (пустое пока) MST одну вершины (у тебя это вершина 1: used[1]=true).

что мы имеем. а имеем мы (1) вершины, которые находятся в MST, (2) вершины, смежные с вершинами в MST (одна из них добавляется в MST на каком-то шагу) и (3) вершины, не смежные с MST (они не могут попасть в MST, не попав вначале в (2) ). вот с различением вершин (2) и вершин (3) у тебя проблемы. нельзя пробежаться по строке матрицы и даже по всей матрице в поисках очередной вершины. там могут встретиться как вершины из 2-й группы так и из 3-ей, а третью группу нельзя использовать.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru