0 / 0 / 0
Регистрация: 12.06.2021
Сообщений: 27
1

Алгоритм Крускала

28.11.2021, 16:04. Показов 533. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Мой код находит вес минимального остовного дерева. Однако у меня проблема в коде, моя проверка проверяет были ли уже посещены вершины, и может оказаться так что результат выводит вес дерева 1-2 3-4-5, то есть путь при 2 и 3 не учитывается при выводе, потому что вершина 2 уже была посещена при нахождении пути от 1 до 2, а вершина 3 была посещена при поиске пути 3-4. Помогите изменить проверку.
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Node 
{
    int start;
    int end;
    int length;
};
bool compare(Node a, Node b)
{
    return a.length < b.length;
}
void Kruskal(vector<Node>& arr, vector<bool>& visited)
{
    int M, N;
    M = visited.size();
    N = arr.size();
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i].start >> arr[i].end >> arr[i].length;
    }
    sort(arr.begin(), arr.end(), compare);
    int weight = 0;
    for (int i = 0; i < N; i++)
    {
        if (!visited[arr[i].start] || !visited[arr[i].end]) // ЭТА САМАЯ ПРОВЕРКА
        {
            weight += arr[i].length;
            visited[arr[i].start] = true;
            visited[arr[i].end] = true;
        }
    }
    cout << "Минимальный вес связующего дерева:";
    cout << weight << endl;
}
int main()
{
    setlocale(LC_ALL, "Russian");
    int M, N, cikl;
    cin >> M >> N;
    vector<Node> arr(N);
    vector<bool> visited(M);
    Kruskal(arr, visited);
    cikl = N - M + 1;
    cout << "Цикломатическое число графа: ";
    cout << cikl;
}
Водные данные
Вершины Ребра
Начало пути Конец пути Вес пути
Пример:
6 8
0 1 7
1 3 2
1 2 1
2 3 2
2 4 3
3 4 6
3 5 1
4 5 8
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.11.2021, 16:04
Ответы с готовыми решениями:

Алгоритм Крускала
Помогите пожалуйста! никак не могу разобраться,при компиляции выдает ошибку: Необработанное...

Алгоритм Крускала
Помогите найти ошибку в алгоритме.Он и работает как то не так и при выводе результатов еще и ошибку...

Алгоритм Крускала
Задача:Порядок ввода:Порядок вывода:Пример ввода:Пример вывода:Органичения:я решил ее с помощью...

Алгоритм, обратный алгоритму Крускала
Требуется реализовать алгоритм поиска максимального остовного дерева

0
28.11.2021, 16:04
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.11.2021, 16:04
Помогаю со студенческими работами здесь

Алгоритм крускала, реализованный в кодеблоке, не запускается в студии
задача: алгоритм крускала #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;windows.h&gt; #include...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная...

Алгоритм Крускала
Ищет связное основное дерево из графа, но не минимальное, не те ребра выбирает. кто подскажет, в...

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

алгоритм Крускала
Помогите пожалуйста реализовать алгоритм Крускала.

Алгоритм Крускала
Здравствуйте! Помогите пожалуйста за небольшое вознаграждение реализовать алгоритм Крускала для...


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

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

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