Форум программистов, компьютерный форум CyberForum.ru

Алгоритм Прима! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 48, средняя оценка - 4.98
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
15.08.2012, 16:55     Алгоритм Прима! #1
И снова здравствуйте! Ознакомился с алгоритмом прима, видел псевдокод, решал примеры, но вот задался вопросом, как реализовать данный алгоритм программно в С++? Изучал статьи, видел реализацию на С++, но в С++ я не эксперт, и многих функций не знаю! Помогите, напишите реализацию и если можно объясните, только доступным языком! Пожалуйста
Знающим в помощь: И объясните чем два варианта алгоритма(см. http://e-maxx.ru/algo/mst_prim) отличаються и где применяются(типы задач)? И где лучше использовать алгоритм Прима, а где алгоритм Дейкстры?
Реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// входные данные
int n;
vector < vector<int> > g;
const int INF = 1000000000; // значение "бесконечность"
 
// алгоритм
vector<bool> used (n);
vector<int> min_e (n, INF), sel_e (n, -1);
min_e[0] = 0;
for (int i=0; i<n; ++i) {
    int v = -1;
    for (int j=0; j<n; ++j)
        if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
            v = j;
    if (min_e[v] == INF) {
        cout << "No MST!";
        exit(0);
    }
 
    used[v] = true;
    if (sel_e[v] != -1)
        cout << v << " " << sel_e[v] << endl;
 
    for (int to=0; to<n; ++to)
        if (g[v][to] < min_e[to]) {
            min_e[to] = g[v][to];
            sel_e[to] = v;
        }
}
Да и как я понял из книги, то алгоритм состоит из этапов:
1. Выбор произвольной вершины графа, поиск ближайшей вершины по весу.
2. Продолжения поиска до конца ребер графа.
Верно я понял, и на чем основано ветвление алгоритма Прима на два варианта?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.08.2012, 16:55     Алгоритм Прима!
Посмотрите здесь:

C++ Алгоритм
Волновой алгоритм (алгоритм Ли) C++
с++ алгоритм C++
C++ Алгоритм прима
Помогите алгоритм для char переделать в алгоритм для float C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
18.08.2012, 21:44  [ТС]     Алгоритм Прима! #2
Может кто поможет, а то довольно сложная тема?
NIch
 Аватар для NIch
399 / 310 / 27
Регистрация: 17.03.2010
Сообщений: 1,120
19.08.2012, 22:43     Алгоритм Прима! #3
И где лучше использовать алгоритм Прима, а где алгоритм Дейкстры?*
Алгоритм Прима для поиска минимального остовного дерева, Дейксты для поиска кратчайшего пути.
ИМХО
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:07  [ТС]     Алгоритм Прима! #4
Цитата Сообщение от NIch Посмотреть сообщение
И где лучше использовать алгоритм Прима, а где алгоритм Дейкстры?*
Алгоритм Прима для поиска минимального остовного дерева, Дейксты для поиска кратчайшего пути.
ИМХО
Вот-вот, я что-то не понял разницы между минимальным остовным деревом и кратчайшем путем. В чем разница?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.08.2012, 06:33     Алгоритм Прима! #5
Цитата Сообщение от mr_free Посмотреть сообщение
Вот-вот, я что-то не понял разницы между минимальным остовным деревом и кратчайшем путем. В чем разница?
разница в том, что остов должен, по определению, содержать п-1 вершин. в то время как минимальный путь может содержать их сколько душе угодно...
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
21.08.2012, 18:21  [ТС]     Алгоритм Прима! #6
То есть остов включает в себя путь только вперед, а путь может быть и вперед и назад, и куда угодно?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.08.2012, 19:31     Алгоритм Прима! #7
не думаю, что понятия "назад" и "вперед" как-то применимы к графам. но вот строго математическое "куда угодно" - в точку.
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
21.08.2012, 20:04  [ТС]     Алгоритм Прима! #8
Цитата Сообщение от salam Посмотреть сообщение
не думаю, что понятия "назад" и "вперед" как-то применимы к графам. но вот строго математическое "куда угодно" - в точку.
Имелось в виду что по пути возможен возврат к исходной вершине?
Перешёл из вершины А в вершину Б, то по пути возможно перейти еще сразу из Б в А?

Добавлено через 39 секунд
salam, может вы еще подскажите с программной реализацией алгоритма примма?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.08.2012, 20:07     Алгоритм Прима! #9
естественно, вопрос в том, насколько это целесообразно.
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
21.08.2012, 20:13  [ТС]     Алгоритм Прима! #10
Цитата Сообщение от salam Посмотреть сообщение
естественно, вопрос в том, насколько это целесообразно.
Так вот, а как насчет реализации?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.08.2012, 20:18     Алгоритм Прима! #11
а что с ней?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.08.2012, 21:03     Алгоритм Прима!
Еще ссылки по теме:

C++ Реализовать алгоритм Прима с бинарной кучей, в которой нужно хранить ребра
C++ алгоритм бм
C++ Графы. Алгоритм Прима

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

Или воспользуйтесь поиском по форуму:
mr_free
 Аватар для mr_free
69 / 3 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
21.08.2012, 21:03  [ТС]     Алгоритм Прима! #12
salam, собственно не могу написать код. Плюс не могу понять работы кода в начале темы, построчно объясните, пожалуйста!
Yandex
Объявления
21.08.2012, 21:03     Алгоритм Прима!
Ответ Создать тему
Опции темы

Текущее время: 16:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru