Решение Задание №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. У вас должна получиться следующая программа:
Протестируйте программу. Отправьте преподавателю скриншот консоли.