Синергия, Структуры и алгоритмы компьютерной обработки данных, задание 1

Решение Задание №1

Задание №1

Дан взвешенный неориентированный граф. Пользователь вводит его в консоль в виде списка рёбер. Напишите программу, которая считает этот граф и сохранит его сперва в виде списка смежности, а потом в виде матрицы смежности.

1. Считайте количество вершин и ребер графа:

int n, m; // количество вершин и ребер

cout << "Enter the number of vertices and edges: ";

cin >> n >> m;

2. Создайте структуры данных для хранения графа: список смежности и матрицу

смежности:

vector<vector<pair<int, int>>> adj_list(n + 1); // список смежности

vector<vector<int>> adj_matrix(n + 1, vector<int>(n + 1)); // матрица смежности

3. Считайте ребра графа и добавьте их в список смежности и матрицу смежности:

cout << "Enter the edges (vertex1 vertex2 weight):" << endl;

for (int i = 0; i < m; i++) {

int v1, v2, w;

cin >> v1 >> v2 >> w;

// добавляем ребро в список смежности

adj_list[v1].push_back({ v2,w });

adj_list[v2].push_back({ v1,w });

// добавляем ребро в матрицу смежности

adj_matrix[v1][v2] = w;

adj_matrix[v2][v1] = w;

}

4. Выведите список смежности на экран:

cout << "Adjacency list:" << endl;

for (int i = 1; i <= n; i++) {

cout << i << ": ";

for (auto j : adj_list[i]) {

cout << "(" << j.first << ", " << j.second << ") ";

}

cout << endl;

}

5. Выведите матрицу смежности на экран:

cout << "Adjacency matrix:" << endl;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

cout << adj_matrix[i][j] << " ";

}

cout << endl;

}

6. У вас должна получиться следующая программа:

Протестируйте программу. Отправьте преподавателю скриншот консоли.