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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Разобраться в функции http://www.cyberforum.ru/cpp-beginners/thread638095.html
Здравствуйте! Имеем функцию на C. Не могу разобраться в строках 17-19 и 30-32. Возможно ли в C++ реализовать их более понятно или хотя бы поясните, как эту функцию перенести в C++, компилятор...
C++ Компилятор С++ Скажите, пожалуйста, каким редактором для написания кода вы пользуетесь, и какой компилятор используете? Напишите недостатки и преимущества вашего выбора. Я начинающий программист, пишу и... http://www.cyberforum.ru/cpp-beginners/thread638093.html
Условие: если строка пустая - выполнить действие C++
Здравствуйте, если можете, помогите создать такое условие: "Условие: если строка пустая - выполнить действие...", на основе этого кода: #include <iostream> using namespace std; int...
C++ Сортировка слиянием (рекурсивный метод) текстовой строки
Привет всем. Возникла трудность не понимаю как отсортировать методом слияний (рекурсивным методом) текстовую строку. К примеру дана строка qwerty qwe qwert qwer И должно получиться следующее qwe...
C++ Ошибка: Stack was corrupted http://www.cyberforum.ru/cpp-beginners/thread638079.html
Здравствуйте уважаемые программисты. Написал простейшую программу заполнения массива и вывода его на консоль. Но при запуске вылазит ошибка (см. прикреплённый файл). Объясните пожалуйста в чём дело?...
C++ Операторы ввода и вывода Допустим есть класс class Checked { public: private: double id; int *beg; std::pair<std::strin, std::strin> par; подробнее

Показать сообщение отдельно
mr_free
70 / 4 / 0
Регистрация: 08.08.2012
Сообщений: 223
Записей в блоге: 1

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

15.08.2012, 16:55. Просмотров 6645. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.