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

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

30.11.2017, 22:45. Показов 19976. Ответов 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
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru