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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 48, средняя оценка - 4.98
mr_free
70 / 4 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
#1

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

15.08.2012, 16:55. Просмотров 6649. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Прима! (C++):

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

Графы. Алгоритм Прима - C++
Начал изучать графы и в месте с ними алгоритм Прима. Суть понял, но разобрать(понять) реализацию на с++ не получилось. решил написать...

Правильный вывод. Алгоритм Прима - C++
Здравствуйте есть код, нужно изменить вывод. #include&lt;conio.h&gt; #include&lt;iostream&gt; using namespace std; int a,b,u,v,n,i,j,ne=1; ...

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

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

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

11
mr_free
70 / 4 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1
18.08.2012, 21:44  [ТС] #2
Может кто поможет, а то довольно сложная тема?
0
NIch
399 / 310 / 27
Регистрация: 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
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
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
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
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
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
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
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
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
Привет! Вот еще темы с ответами:

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i&gt;=0; i--) { str = (x&amp;1 == 1) ? '1' : '0'; x = x &gt;&gt;...


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

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

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