Необходимо объединить два кода в один

@master_hamster · Регистрация: 14.12.2021

Студворк — интернет-сервис помощи студентам

Помогите объединить два кода в один

Алгоритм Прима:

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
#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e9 + 7;
 
vector<pair<int, int>> graph[100000];
bool used[100000];      //включили ли мы соответствующую вершину в остов
 
int main() {
    //Ввод графа...
 
    int mst_weight = 0;     //Текущий вес остова.
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
 
    q.push({0, 0});     //Начнём с вершины 0.
 
    while (!q.empty()) {
        pair<int, int> c = q.top();
        q.pop();
 
        int dst = c.first, v = c.second;
 
        if (used[v]) {      //вершина уже добавлена в остов
            continue;
        }
 
        used[v] = true;
        mst_weight += dst;
 
        for (pair<int, int> e: graph[v]) {
            int u = e.first, len_vu = e.second;
 
            if (!used[u]) {
                q.push({len_vu, u});    //Заметьте: мы учитываем только длину ребра.
            }
        }
    }
 
    cout << "Minimum spanning tree weight: " << mst_weight << endl;
}

Генерация и вывод графа:

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
#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <queue>
 
using namespace std;
 
using Vec = vector<int>;
using Matrix = vector<Vec>;
 
struct Edge
{
    int i;
    int j;
    int cost;
};
 
Matrix get_random_graph(int n)
{
    mt19937 engine { random_device()() } ;
    uniform_int_distribution<int> uid(1, 10);
    Matrix adj(n, Vec(n));
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            adj[i][j] = adj[j][i] = uid(engine);
        }
    }
    return adj;
}
 
void print(const Matrix& m, const string& title) //Вывод графа
{
    cout << title << "\n";
    for (const auto& row : m)
    {
        for (const auto item : row)
        {
            cout << item << "\t";
        }
        cout << "\n";
     }
}
 
int main()
{
    int n;
    cout << "Enter n: ";
    cin >> n;
    Matrix adj = get_random_graph(n);
    print(adj, "Graph");
    return 0;
}

@Kuzia domovenok · 22.12.2021, 17:07

Модератор, тут форумчанин плодит повторы тем. Генерация графа и алгоритм Прима
master_hamster, Зачем новую тему создавать? Если ты думаешь, что твои старые мало народу посмотрело, это не так. Там под 200 человек просмотров.

@master_hamster · 22.12.2021, 17:18 **[ТС]**

Kuzia domovenok, просто мне очень нужна помощь

Добавлено через 6 минут
Извините

@lemegeton · 23.12.2021, 13:38

Сообщение от master_hamster

vector<pair<int, int>> graph[100000];

Это сто тыщ списков смежности?! )))

У вас первый код находит минимальное остовное дерево через список смежности, а второй код генерирует матрицу смежности.

Проверьте правильность работы, пожалуйста.

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
#include <iostream>
#include <random>
#include <iomanip>
 
template<typename T>
using Row = std::vector<T>;
 
template<typename T>
using Matrix = std::vector<Row<T>>;
 
template<typename T>
Matrix<T> create(size_t height, size_t width, const T &initial) {
    return std::move(Matrix<T>{height, Row<T>(width, initial)});
}
 
template<typename T>
std::ostream &operator<<(std::ostream &out, const Matrix<T> &m) {
    for (const auto &row : m) {
        for (const auto &i : row) {
            out << std::fixed << std::setprecision(2) << std::setw(7) << i;
        }
        out << std::endl;
    }
    return out;
}
 
struct Random {
    std::random_device randomDevice;
    std::mt19937 randomEngine;
    std::uniform_real_distribution<double> distribution;
    Random(double min, double max): randomDevice{}, randomEngine{randomDevice()}, distribution(min, max) {}
    double operator()() {
        return distribution(randomEngine);
    }
};
 
template<typename T>
Random &operator>>(Random &r, Matrix<T> &m) {
    for (std::size_t i = 0; i < m.size(); ++i) {
        for (std::size_t j = i + 1; j < m[i].size(); ++j) {
            m[i][j] = m[j][i] = r();
        }
    }
    return r;
}
 
template<typename T>
Matrix<T> minSpanningTree(const Matrix<T> &source) {
    Matrix<T> result = create(source.size(), source.size(), 0.0);
    std::vector<bool> visited(source.size(), false);
    visited[0] = true;
    std::size_t count = 0;
    while (count < source.size() - 1) {
        double min = std::numeric_limits<double>::infinity();
        std::size_t min_i = 0;
        std::size_t min_j = 0;
        for (std::size_t i = 0; i < source.size(); ++i) {
            if (visited[i]) {
                for (std::size_t j = 0; j < source.size(); ++j) {
                    if (!visited[j] && source[i][j] != 0) {
                        if (min > source[i][j]) {
                            min = source[i][j];
                            min_i = i;
                            min_j = j;
                        }
                    }
                }
            }
        }
        result[min_i][min_j] = result[min_j][min_i] = source[min_i][min_j];
        visited[min_j] = true;
        ++count;
    }
    return std::move(result);
}
 
int main() {
    Matrix<double> adjacency = create(5, 5, 0.0);
 
    Random random{0, 10};
 
    random >> adjacency;
    std::cout << "SOURCE ADJ MATRIX:" << std::endl << adjacency << std::endl;
 
    Matrix<double> result = minSpanningTree(adjacency);
    std::cout << "MIN SPANNING TREE:" << std::endl << result << std::endl;
 
    return 0;
}

@master_hamster · 23.12.2021, 16:23 **[ТС]**

lemegeton, Вы меняя не совсем правильно поняли. Мне нужен граф с целыми числами.
Также вот пример вывода минимального остовного дерева:
1 --> 2 --> 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
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
99
100
101
#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <queue>
#include <conio.h>
 
using Vec = std::vector<int>;
using Matrix = std::vector<Vec>;
 
int a, b, u, v, n, i, j;
int ne = 1;
int visited[10] = {0};
int min;
int mincost = 0;
int cost[10][10];
 
struct Edge
{
    int i;
    int j;
};
 
Matrix get_random_graph(int n)
{
    std::mt19937 engine { std::random_device()() } ;
    std::uniform_int_distribution<int> uid(1, 10);
    Matrix cost(n, Vec(n));
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            cost[i][j] = cost[j][i] = uid(engine);
        }
    }
    return cost;
}
 
void print(const Matrix& m, const std::string& title)
{
    std::cout << title << "\n";
    for (const auto& row : m)
    {
        for (const auto item : row)
        {
            std::cout << item << "\t";
        }
        std::cout << "\n";
     }
}
 
int main()
{
  int path[100] = {0}; //В этот массив будут записываться вершины, по которым составиться путь
  int path_index = 0;
 
  std::cout << "Enter the number of vertices: "; //Введи количество вершин:
  std::cin >> n;
  Matrix adj = get_random_graph(n);
    print(adj, "Graph");
 
  visited[1] = 1;
  std::cout << "\n";
 
  while(ne < n)
  {
    for(i = 1, min = 999; i <= n; i++)
    for(j = 1; j <= n; j++)
    if(cost[i][j] < min)
    if(visited[i] != 0)
    {
      min = cost[i][j];
      a = u = i;
      b = v = j;
    }
    if(visited[u] == 0 || visited[v] == 0)
    {
      path[path_index] = b;
      path_index++;
      //cout<<"\n "<<ne++<<"  "<<a<<"  "<<b<<min; //Можно вывести так
      ne++; //если строчку выше раскомментировать - эту закомментировать
      mincost += min;
      visited[b] = 1;
 
    }
    cost[a][b] = cost[b][a] = 999;
  }
 
  std::cout << "Minimum spanning tree\n"; //Минимальное остовное дерево
  std::cout << 1 << " --> ";
  for(int i = 0; i < n-1; i++)
  {
    std::cout << path[i];
    if(i < n-2)
    {
      std::cout<<" --> ";
    }
  }
  std::cout << "\nMinimum cost " << mincost; //Минимальная стоимость
  std::cin.get();
}

@lemegeton · 23.12.2021, 19:22

Сообщение от master_hamster

Также вот пример вывода минимального остовного дерева:
1 --> 2 --> 3 --> 4

Как будет выглядеть такой вывод, если в дереве будет еще ребро 2-5?

Сообщение от master_hamster

Мне нужен граф с целыми числами.

Переделать мой код на целые числа не должно быть такой уж проблемой.

Добавлено через 4 минуты

Сообщение от master_hamster

Также вот пример вывода минимального остовного дерева:
1 --> 2 --> 3 --> 4

Обратите внимание, что минимальное остовное дерево это граф (не путь, например).
Граф не получится вывести только как последовательность вершин.
Зато можно матрицей смежности (как у меня) или списком смежности (пары вершин и вес).

@master_hamster · 23.12.2021, 19:37 **[ТС]**

lemegeton, В этом коде всё верно. Только тут граф нужно вводить вручную, а мне нужна генерация. Возможно этот код можно сделать с генерацией графика?

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
#include<iostream>
#include<conio.h>
 
int a, b, u, v, n, i, j;
int ne = 1;
int visited[10] = {0};
int min;
int mincost = 0;
int cost[10][10];
 
int main()
{
    int path[100] = {0}; //В этот массив будут записываться вершины, по которым составиться путь
    int path_index = 0;
 
    std::cout << "Enter the number of vertices: "; //Введи количество вершин:
    std::cin >> n;
    std::cout << "Enter the matrix\n"; //Введи матрицу
 
    for(i = 1; i <= n; i++)
    for(j = 1; j <= n; j++)
    {
        std::cin >> cost[i][j];
        if(cost[i][j] == 0)
        {
            cost[i][j] = 999; //999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе
        }
    }
    visited[1] = 1;
    std::cout << "\n";
 
    while(ne < n)
    {
        for(i = 1, min = 999; i <= n; i++)
        for(j = 1; j <= n; j++)
        if(cost[i][j] < min)
        if(visited[i] != 0)
        {
            min = cost[i][j];
            a = u = i;
            b = v = j;
        }
        if(visited[u] == 0 || visited[v] == 0)
        {
            path[path_index] = b;
            path_index++;
            //cout<<"\n "<<ne++<<"  "<<a<<"  "<<b<<min; //Можно вывести так
            ne++; //если строчку выше раскомментировать - эту закомментировать
            mincost += min;
            visited[b] = 1;
 
        }
        cost[a][b] = cost[b][a] = 999;
    }
 
    std::cout << "Minimum spanning tree\n"; //Минимальное остовное дерево
    std::cout << 1 << " --> ";
    for(int i = 0; i < n-1; i++)
    {
        std::cout << path[i];
        if(i < n-2)
        {
            std::cout<<" --> ";
        }
    }
    std::cout << "\nMinimum cost " << mincost; //Минимальная стоимость
    std::cin.get();
}

Добавлено через 3 минуты
Наверное в вышепредставленном коде матрица смежности?

Добавлено через 6 минут
с генерацией графа*

@lemegeton · 23.12.2021, 19:43

Сообщение от master_hamster

Вы меняя не совсем правильно поняли.

Так вы мне ничего и не говорили. Приходится додумывать за вас ибо спрашивать в 99% бесполезно.
Пишите, пожалуйста, задание и ограничения целиком и сразу. Переделывать никто не любит.

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
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <random>
#include <iomanip>
 
template<typename T>
using Row = std::vector<T>;
 
template<typename T>
using Matrix = std::vector<Row<T>>;
 
template<typename T>
Matrix<T> create(size_t height, size_t width, const T &initial) {
    return std::move(Matrix<T>{height, Row<T>(width, initial)});
}
 
template<typename T>
std::ostream &operator<<(std::ostream &out, const Matrix<T> &m) {
    for (const auto &row : m) {
        for (const auto &i : row) {
            out << std::fixed << std::setprecision(2) << std::setw(7) << i;
        }
        out << std::endl;
    }
    return out;
}
 
struct Random {
    std::random_device randomDevice;
    std::mt19937 randomEngine;
    std::uniform_real_distribution<double> distribution;
    Random(double min, double max): randomDevice{}, randomEngine{randomDevice()}, distribution(min, max) {}
    double operator()() {
        return distribution(randomEngine);
    }
};
 
template<typename T>
Random &operator>>(Random &r, Matrix<T> &m) {
    for (std::size_t i = 0; i < m.size(); ++i) {
        for (std::size_t j = i + 1; j < m[i].size(); ++j) {
            m[i][j] = m[j][i] = r();
        }
    }
    return r;
}
 
template<typename T>
Matrix<T> minSpanningTree(const Matrix<T> &source) {
    Matrix<T> result = create(source.size(), source.size(), T{});
    std::vector<bool> visited(source.size(), false);
    visited[0] = true;
    std::size_t count = 0;
    while (count < source.size() - 1) {
        double min = std::numeric_limits<double>::infinity();
        std::size_t min_i = 0;
        std::size_t min_j = 0;
        for (std::size_t i = 0; i < source.size(); ++i) {
            if (visited[i]) {
                for (std::size_t j = 0; j < source.size(); ++j) {
                    if (!visited[j] && source[i][j] != 0) {
                        if (min > source[i][j]) {
                            min = source[i][j];
                            min_i = i;
                            min_j = j;
                        }
                    }
                }
            }
        }
        result[min_i][min_j] = result[min_j][min_i] = source[min_i][min_j];
        visited[min_j] = true;
        ++count;
    }
    return std::move(result);
}
 
template<typename T>
struct AsAdjList {
    const Matrix<T> &matrix;
};
 
template<typename T>
std::ostream &operator<<(std::ostream &out, AsAdjList<T> wrapper) {
    for (std::size_t i = 0; i < wrapper.matrix.size() - 1; ++i) {
        for (std::size_t j = i + 1; j < wrapper.matrix.size(); ++j) {
            if (wrapper.matrix[i][j] != 0) {
                out << "{" << i << "-->" << j << ": " << wrapper.matrix[i][j] << "}" << std::endl;
            }
        }
    }
    return out;
}
 
int main() {
    Matrix<int> adjacency = create(5, 5, 0);
 
    Random random{0, 10};
 
    random >> adjacency;
    std::cout << "SOURCE ADJ MATRIX:" << std::endl << adjacency << std::endl;
 
    Matrix<int> result = minSpanningTree(adjacency);
    std::cout << "MIN SPANNING TREE:" << std::endl << result << std::endl;
    std::cout << "MIN SPANNING TREE ADJ LIST:" << std::endl << AsAdjList<int>{result} << std::endl;
 
    return 0;
}

Добавлено через 5 минут

Сообщение от master_hamster

Наверное в вышепредставленном коде матрица смежности?

В вышепредставленном коде непонятно что происходит. Там выводятся какие-то вершины подряд.
Как это может представлять собой граф, коим является остовное дерево, мне не совсем понятно.

@master_hamster · 23.12.2021, 19:44 **[ТС]**

lemegeton, спасибо большое за помощь и за терпение). Можно ещё вопрос не совсем по теме?

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	22.12.2021, 17:07
	Модератор, тут форумчанин плодит повторы тем. Генерация графа и алгоритм Прима master_hamster, Зачем новую тему создавать? Если ты думаешь, что твои старые мало народу посмотрело, это не так. Там под 200 человек просмотров. 1

@master_hamster 0 / 0 / 0 Регистрация: 14.12.2021 Сообщений: 57
	22.12.2021, 17:18 [ТС]
	Kuzia domovenok, просто мне очень нужна помощь Добавлено через 6 минут Извините 0

@master_hamster 0 / 0 / 0 Регистрация: 14.12.2021 Сообщений: 57
	23.12.2021, 19:44 [ТС]
	lemegeton, спасибо большое за помощь и за терпение). Можно ещё вопрос не совсем по теме? 0

Необходимо объединить два кода в один

Решение