Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
wickedqwe
0 / 0 / 1
Регистрация: 02.02.2015
Сообщений: 1
#1

Графы. Алгоритм Прима - C++

02.02.2015, 12:10. Просмотров 2566. Ответов 1
Метки нет (Все метки)

Начал изучать графы и в месте с ними алгоритм Прима. Суть понял, но разобрать(понять) реализацию на с++ не получилось.
решил написать свою.
Это полноценный алгоритм Прима?
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
52
#include <fstream>
#include<iostream>
 using namespace std;
 
 const int MAX = 2000000000;
void main()
{
    setlocale(LC_ALL, "Rus");
    int n;   // размер матрицы смежностей
    ifstream fin("input.txt");
    fin >> n;
    int **graph = new int*[n];      //
    for (int i = 0; i < n; i++) {   //матрица смежности
        graph[i] = new int[n];      //
    }                               //
    bool *visited = new bool[n];// масив хранящий вершины уже добавлиные в минимальное островное дерево
 
    for (int i = 0; i < n; i++) {    //считуем матрицу с файла
        for (int j = 0; j < n; j++) {
            fin >> graph[i][j];
            if (graph[i][j] == 0)
                graph[i][j] = MAX; // нули меняем на 'бесконечность'
        }
        visited[i] = false;  //инициализация - вершин добавленых в дерево нет
    }
    fin.close();
 
    int v1, v2; // v1-вершина уже добавленая, v2 - будет добавлена
    int min;
    visited[0] = true; // добавляем в дерево первую вершину
    for (int tek = 1; tek < n; tek++) { // повторяем н - 1 раз(н - 1 : оставшееся количество вершин)
        min = MAX; // мин = *бесконечность*
        for (int i = 0; i < n; i++) { // тут ищем потенциально возможные новые рёбра для дерева, для минимального ребра сохраняем вершины при нем
            if (visited[i] == true) {
    
                for (int d = 0; d < n; d++) {
                    if (min > graph[i][d] && !visited[d]) {
                        v1 = i;
                        min = graph[i][d];
                        v2 = d;
                    }
                }
            }
        }
        cout << endl << v1 << ' ' << v2; 
        visited[v2] = true;
    }
    ////////////
    for (int i = 0; i < n; i++)
        delete [] graph[i];
    system("pause");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2015, 12:10
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Графы. Алгоритм Прима (C++):

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

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

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

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

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

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

1
Nelo_001
4 / 6 / 6
Регистрация: 31.10.2013
Сообщений: 177
16.04.2015, 20:46 #2
нет

C++
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 
0 4 6 10 0 0 0 0 0 0 0 
4 0 0 0 15 5 0 0 0 0 0
6 0 0 0 6 0 5 0 0 0 0 
10 0 0 0 0 5 11 0 0 0 0 
0 15 6 0 0 0 0 13 11 0 0 
0 5 0 5 0 0 0 8 0 7 0 
0 0 5 11 0 0 0 0 8 8 0
0 0 0 0 13 8 0 0 0 0 10
0 0 0 0 11 0 8 0 0 0 13 
0 0 0 0 0 7 8 0 0 0 7
0 0 0 0 0 0 0 10 13 7 0
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.04.2015, 20:46
Привет! Вот еще темы с решениями:

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

Графы. Алгоритм
Определить, можно ли в заданной системе односторонних дорог проехать из города...

Графы. Нужно составить алгоритм
Помогите алгоритмизировать задачу! Нужно написать программу способную...

Графы, алгоритм Диница (реализовать граф списком смежности)
У меня есть готовая программа по алгоритму Диница, но граф в матричном...


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

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

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