Форум программистов, компьютерный форум CyberForum.ru

Агоритм крускала - C++

Восстановить пароль Регистрация
 
dk61
0 / 0 / 0
Регистрация: 14.05.2013
Сообщений: 4
11.07.2013, 00:53     Агоритм крускала #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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
bool Choose(int **Ribs, int x, int y, int Dimension){// проверка существования пути между точкой x и y
    int **RibsWave;
    RibsWave = Ribs;
    for (int i = 0; i < Dimension; i++)
        for (int j = 0; j < Dimension; j++)
            if (RibsWave[i][j] != 0)
                RibsWave[i][j] = 1;
    RibsWave[x][x]= 1;
    RibsWave[y][y]= 1;
}
 
void algorithmKryskala (int **Table, int Dimension, int **Ribs, int& Sum){ // Главная таблица, размерность, Таблица остовного дерева
    Sum = 0; // Размер остовного дерева
    RibsArr *SortRibs; //Отсортированный массив всех рёбер
    int NumRibs = 0; //Расчёт числа рёбер
    for (int i = 0; i < Dimension; i++)
        for (int j = 0; j < Dimension; j++)
            if (Table[i][j] != 0){
                NumRibs += 1;
            }
    NumRibs /= 2;
    SortRibs = new RibsArr[NumRibs];
    for (int i = 0; i < NumRibs; i++)
        SortRibs[i].w = 0;
    bool F;
    int l = 0;
    int Min=9999;
    for (int i = 0; i < Dimension; i++){ //Закидываем рёбра в структуру SortRibs
        for (int j = 0; j < Dimension; j++){
            if (Table[i][j] != 0){
                F = false;
                for (int k = 0; k < l+1; k++){
                    if (Table[i][j] == SortRibs[k].w){
                        if ((i == SortRibs[k].x && SortRibs[k].y == j) || (i == SortRibs[k].y && SortRibs[k].x == j))
                            F = true;
                    }
                }
                if (F == false){
                    SortRibs[l].w = Table[i][j];
                    SortRibs[l].x = i;
                    SortRibs[l].y = j;
                    l += 1;
                }
            }
        }
    }
    if (NumRibs > 1){
        do{ //Сортировка SortRibs
            F = false;
            for (int i = 0; i < NumRibs-1; i++)
                if (SortRibs[i].w > SortRibs[i+1].w){
                    RibsArr Temp;
                    Temp = SortRibs[i];
                    SortRibs[i] = SortRibs[i+1];
                    SortRibs[i+1] = Temp;
                    F = true;
                }
        }
    while ( F == true);
    }
    for (int i = 0; i < NumRibs-1; i++){ // Проверка наличия пути между x и y если нет то добавляем данное ребро в матрицу Ribs
        if (Choose){
            Ribs[SortRibs[i].x][SortRibs[i].y] = SortRibs[i].w;
            Ribs[SortRibs[i].y][SortRibs[i].x] = SortRibs[i].w;
        }
    }
    cout << endl;   
}
    
void main (){
    setlocale(LC_ALL, "RUS");
    cout << "Введите размерность" << endl;
    int Dimension;
    cin >> Dimension;   //Ввод размерность
    int **Table;    //Создание Главной таблицы, и Остовной таблицы
    Table = new int*[Dimension];
    int **Ribs;
    Ribs = new int*[Dimension];
    for (int i = 0; i < Dimension; i++){
        Table[i] = new int[Dimension];
        Ribs[i] = new int[Dimension];
        for (int j = 0; j < Dimension; j++) // Заполнение остовной таблицы нулями
            Ribs[i][j]=0;
    }
    for (int i = 0; i < Dimension; i++)
        for (int j = 0; j < Dimension; j++)
            cin >> Table[i][j];
    int Sum;
    Sum = 0;
    algorithmKryskala (Table, Dimension, Ribs, Sum); //Запуск алгоритма крускала и вывод суммы
    for (int i = 0; i < Dimension; i++){
        for (int j = 0; j < Dimension; j++)
            cout << Ribs[i][j] << " ";
        cout << endl;
    }
    cout << "sum=" << Sum;
    system ("PAUSE");
}
Вся проблема в функции Choose, если кто сможет помогите пожалуйста, заранее спасибо

Добавлено через 25 минут
Всё не решайте, мне подсказали решение)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2013, 00:53     Агоритм крускала
Посмотрите здесь:

Алгоритм Крускала
Turbo Pascal Агоритм разветвляющей структуры
Алгоритм Крускала C++
C++ Алгоритм Крускала
Линейный агоритм.Неверный результат Delphi
Алгоритм Крускала и Прима
Алгоритм, обратный алгоритму Крускала C++
Алгоритм Крускала (Краскала) на Assembler

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 03:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru