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

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

02.02.2015, 12:10. Показов 5524. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.02.2015, 12:10
Ответы с готовыми решениями:

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

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

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

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

1
6 / 8 / 7
Регистрация: 31.10.2013
Сообщений: 217
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.04.2015, 20:46

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru