Lesson_07/Task_2/Task_2.cpp - master - AirLexa/03

Lesson_07/Task_2/Task_2.cpp
77 строк3 KB
AirLexa
загрузил Lesson_07/Task_2/Task_2.cpp
23 янв 2026, 14:57
23 янв 2026, 14:574f95d99
#include <iostream>
#include <fstream>
#include <queue>
#include <windows.h>

int main()
{
	SetConsoleCP(1251);
	SetConsoleOutputCP(1251);

	std::ifstream file("input.txt"); // файл инициализации в папке с исполняемым файлом

	if (!file.is_open()) // проверка на доступ к файлу
	{
		std::cout << "Ошибка открытия файла: input.txt!" << std::endl;
		return -1;
	}

	int size = 0;

	file >> size; // первая строчка - это размер массива
	if (size <= 1) // проверка на корректность значений размера
	{
		std::cout << "Ошибка! Количество вершин графа должно быть 2 или больше!" << std::endl;
		return -2;
	}
	// двухмерный массив
	bool** arr = new bool* [size]; // пользуемся тем, что 0 = false, !0 = true
	for (int i = 0; i < size; i++)
	{
		arr[i] = new bool[size]();
		for (int j = 0; j < size; j++) // заполняем массив данными
			file >> arr[i][j];
	}
	file.close(); // файл больше не понадобится

	std::cout << "Исходная матрица смежности:\n";
	for (int i = 0; i < size; i++) // выводим массив на консоль
	{
		for (int j = 0; j < size; j++)
			std::cout << arr[i][j] << " ";
		std::cout << std::endl;
	}
	int n = 0;
	std::cout << "В графе " << size 
		<< " вершин. Введите номер вершины, с которой начнётся обход: ";
	std::cin >> n;
	if (n-- > size || n < 0) // проверка на корректность значений номера
	{
		std::cout << "Ошибка! Такой вершины не существует!" << std::endl;
		return -3;
	}
	bool* check = new bool[size](); // массив хранения посещенных вершин

	std::queue<int> q; // очередь вершин для посещения
	q.push(n); // кладем туда то что ввели с консоли
	check[n] = true; // записываем вершину в посещенные
	std::cout << "Порядок обхода вершин:";
	while (!q.empty()) { // пока очередь не пуста
		int cur = q.front();  // извлекаем первого из очереди
		q.pop(); // и сдвигаем ее
		std::cout << " " << (cur + 1); // выводим вершину на экран
		for (int i = 0; i < size; i++) //добавляем в очередь всех непосещённых соседей.
			if (arr[cur][i] && !check[i]) { // если есть ребро и еще не посещали
				q.push(i); // добавляем эту вершину в очередь
				check[i] = true; // отмечаем посещение
			}
	}
	std::cout << std::endl;

	for (int i = 0; i < size; i++) // освобождаем память
		delete[] arr[i];
	delete[] arr;
	delete[] check;

	return 0;
}