Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/40: Рейтинг темы: голосов - 40, средняя оценка - 4.60
mr_free
70 / 4 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
#1

Алгоритм Прима!

15.08.2012, 16:55. Просмотров 7114. Ответов 11
Метки нет (Все метки)

И снова здравствуйте! Ознакомился с алгоритмом прима, видел псевдокод, решал примеры, но вот задался вопросом, как реализовать данный алгоритм программно в С++? Изучал статьи, видел реализацию на С++, но в С++ я не эксперт, и многих функций не знаю! Помогите, напишите реализацию и если можно объясните, только доступным языком! Пожалуйста
Знающим в помощь: И объясните чем два варианта алгоритма(см. 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. Продолжения поиска до конца ребер графа.
Верно я понял, и на чем основано ветвление алгоритма Прима на два варианта?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.08.2012, 16:55
Ответы с готовыми решениями:

Алгоритм прима
Всем привет! Помогите пожалуйста реализовать алгоритм Прима, для нахождения...

Графы. Алгоритм Прима
Начал изучать графы и в месте с ними алгоритм Прима. Суть понял, но...

Правильный вывод. Алгоритм Прима
Здравствуйте есть код, нужно изменить вывод. #include&lt;conio.h&gt;...

Алгоритм Прима. Минимальное островное дерево
Всем доброго времени суток. Сейчас нахожусь в полной фрустрации, т.к уже пару...

Минимальное островное дерево. Алгоритм Прима
Нужна реализация алгоритма Прима по матрице смежности данного графа.Не нашел...

11
mr_free
70 / 4 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
18.08.2012, 21:44  [ТС] #2
Может кто поможет, а то довольно сложная тема?
0
NIch
400 / 311 / 74
Регистрация: 17.03.2010
Сообщений: 1,120
19.08.2012, 22:43 #3
И где лучше использовать алгоритм Прима, а где алгоритм Дейкстры?*
Алгоритм Прима для поиска минимального остовного дерева, Дейксты для поиска кратчайшего пути.
ИМХО
0
mr_free
70 / 4 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
20.08.2012, 22:07  [ТС] #4
Цитата Сообщение от NIch Посмотреть сообщение
И где лучше использовать алгоритм Прима, а где алгоритм Дейкстры?*
Алгоритм Прима для поиска минимального остовного дерева, Дейксты для поиска кратчайшего пути.
ИМХО
Вот-вот, я что-то не понял разницы между минимальным остовным деревом и кратчайшем путем. В чем разница?
0
salam
175 / 156 / 29
Регистрация: 10.07.2012
Сообщений: 766
21.08.2012, 06:33 #5
Цитата Сообщение от mr_free Посмотреть сообщение
Вот-вот, я что-то не понял разницы между минимальным остовным деревом и кратчайшем путем. В чем разница?
разница в том, что остов должен, по определению, содержать п-1 вершин. в то время как минимальный путь может содержать их сколько душе угодно...
0
mr_free
70 / 4 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
21.08.2012, 18:21  [ТС] #6
То есть остов включает в себя путь только вперед, а путь может быть и вперед и назад, и куда угодно?
0
salam
175 / 156 / 29
Регистрация: 10.07.2012
Сообщений: 766
21.08.2012, 19:31 #7
не думаю, что понятия "назад" и "вперед" как-то применимы к графам. но вот строго математическое "куда угодно" - в точку.
0
mr_free
70 / 4 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
21.08.2012, 20:04  [ТС] #8
Цитата Сообщение от salam Посмотреть сообщение
не думаю, что понятия "назад" и "вперед" как-то применимы к графам. но вот строго математическое "куда угодно" - в точку.
Имелось в виду что по пути возможен возврат к исходной вершине?
Перешёл из вершины А в вершину Б, то по пути возможно перейти еще сразу из Б в А?

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

Алгоритм Прима для построения максимального дерева
Алгоритм Прима.С++

Реализовать алгоритм Прима с бинарной кучей, в которой нужно хранить ребра
Здравствуйте уважаемые программисты тут вот такая задачка попалась нужно...

Реализация алгоритма Прима
Алгоритм Прима?кто может написать?


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru