С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/103: Рейтинг темы: голосов - 103, средняя оценка - 4.83
1 / 1 / 2
Регистрация: 16.12.2016
Сообщений: 149

Минимальное островное дерево. Алгоритм Прима

30.11.2017, 22:45. Показов 19920. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Нужна реализация алгоритма Прима по матрице смежности данного графа.Не нашел ничего подходящего .(си-плюс-плюс-сначала.ру не кидать)
Миниатюры
Минимальное островное дерево. Алгоритм Прима  
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
30.11.2017, 22:45
Ответы с готовыми решениями:

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

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

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

7
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
01.12.2017, 11:36
Лучший ответ Сообщение было отмечено m4ksc0r как решение

Решение

островное

Добавлено через 12 часов 31 минуту
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
    vector< vector<int> > graph = {
        { 0, 5, 0, 0, 0, 4, 6, 0, 0, 0 },
        { 5, 0,10, 2, 0, 0, 0, 0, 0, 0 },
        { 0,10, 0, 0,12, 0, 0, 0, 0, 0 },
        { 0, 2, 0, 0, 9,11, 0, 0, 4, 0 },
        { 0, 0,12, 9, 0, 0, 0, 0, 5, 0 },
        { 4, 0, 0,11, 0, 0, 0,15,13, 0 },
        { 6, 0, 0, 0, 0, 0, 0,16, 0, 9 },
        { 0, 0, 0, 0, 0,15,16, 0,10, 5 },
        { 0, 0, 0, 4, 5,13, 0,10, 0,11 },
        { 0, 0, 0, 0, 0, 0, 9, 5,11, 0 }
    };
    set<int> SP = {}, SM = {0,1,2,3,4,5,6,7,8,9};
 
    int min = numeric_limits<int>::max();
    int l, t;
    
    for (auto i = 0; i < graph.size(); ++i)
        for (auto j = i; j < graph.size(); ++j)
            if (graph[i][j] < min && graph[i][j]!=0)
            {
                min = graph[i][j];
                l = i;
                t = j;
            }
    cout << "[" << l + 1 << ", " << t + 1 << " ];  ";
    SP.insert(l);   SM.erase(l);
    SP.insert(t);   SM.erase(t); 
    while (!SM.empty()) 
    {
        min = numeric_limits<int>::max();
        l = t = 0;
        for (auto i:SM)
            for(auto j: SP)
                if (graph[i][j]<min && graph[i][j] != 0)
                    {
                        min = graph[i][j];
                        l = i;
                        t = j;
                    }
        SP.insert(l);   SM.erase(l);
        cout << "[" << l+1 << ", " << t+1 << " ];  ";
    }
    system("pause");
    return 0;
}
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
04.12.2017, 00:57
0 реакции? чё за...
0
1 / 1 / 2
Регистрация: 16.12.2016
Сообщений: 149
07.12.2017, 21:50  [ТС]
Kuzia domovenok, спасибо большое,просто не заходил на форум. Возможно сделать вывод минимального пути в виде 1->2->3->...n ?

Добавлено через 32 минуты
без vector можно реализовать?
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
07.12.2017, 22:47
m4ksc0r, а что тут от векторов такого используется, что нельзя заменить массивом? Ни одного метода вектора! Даже ни единого push_back нету! Можно смело подменять массивом.

Вообще странно, что тебя смущает вектор, который полностью аналогичен 2д массиву, а тот же set, вокруг которого крутится весь алгоритм ты даже не заметил!

Добавлено через 1 минуту
Цитата Сообщение от m4ksc0r Посмотреть сообщение
Возможно сделать вывод минимального пути в виде 1->2->3->...n ?
пути откуда куда? Алгоритм Прима не работает с путями.
0
1 / 1 / 2
Регистрация: 16.12.2016
Сообщений: 149
07.12.2017, 22:50  [ТС]
Kuzia domovenok, ни разу не встречал такой реализации
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
07.12.2017, 22:54
m4ksc0r, а какие встречал?
0
7 / 7 / 3
Регистрация: 23.12.2014
Сообщений: 94
30.03.2019, 16:00
Реализация без vector/set
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
#include <iostream>
using namespace std;
 
void main(){
    int mass[7][7] = {{0,7,0,5,0,0,0},
                        {7,0,8,9,7,0,0},
                        {0,8,0,0,5,0,0},
                        {5,9,0,0,15,6,0},
                        {0,7,5,15,0,8,9},
                        {0,0,0,6,8,0,11},
                        {0,0,0,0,9,11,0}};
    
    int n=7;
    bool *visited = new bool[n];
    memset(visited,false,sizeof(bool)*n);
    visited[0] = true;
    for(int l=0; l<n-1; l++){
        int minx = -1 , miny = -1 ;
        for(int i=0; i<n; i++)
            if(visited[i])
                for(int j=0; j<n; j++)
                    if(!visited[j] && mass[i][j] > 0 && (miny == -1 || mass[i][j] < mass[miny][minx]))
                        miny = i, minx = j;     
        visited[minx] = true;
        cout << miny << ' ' << minx << endl;
    }
 
    system("pause");
}
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
30.03.2019, 16:00
Помогаю со студенческими работами здесь

Алгоритм Прима
Помогите пожалуйста исправить ошибки |34|error: invalid conversion from 'int' to 'int**' |50|error: invalid conversion from 'int' to...

Алгоритм Прима!
И снова здравствуйте! Ознакомился с алгоритмом прима, видел псевдокод, решал примеры, но вот задался вопросом, как реализовать данный...

Найти минимальное остовное дерево с помощью алгоритмов Прима и Краскала.
Найти минимальное остовное дерево с помощью алгоритмов Прима и Краскала для графа,заданного матрицей весов

Найти двумя методами (Краскала и Прима) минимальное остовное дерево графа
Найти двумя методами (Краскала и Прима) минимальное остовное дерево графа.

Построить минимальное дерево-остов графа пошагово аналитически и реализовать данный алгоритм
Построить минимальное дерево-остов графа пошагово аналитически и реализовать данный алгоритм на Pascal.


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru