Лабораторная работа: (C++) «Графы» вариант 29

Задание:

Разработать программу поиска в графе в соответствии с вариантом задания (Табл. 1).

Провести тестирование качества разработанной программы в соответствии с планом тестирования.

Тестовые данные составляются самостоятельно.

Общий алгоритм работы программы:

Чтение входного файла и формирование в памяти графа.

Работа с графом в соответствии с индивидуальном заданием.

Запись результатов в выходной файл.

По окончании работы программа выводит в консоль время работы в миллисекундах.

Требования к входным и выходным данным

Выходные данные. По окончании работы программа выводит 1 беззнаковое целое число, и перевод строки (std::endl или “n”). Никакой другой текстовой или числовой информации, или единиц измерения не выводится.

Команда запуска программы:

graphsearch.exe имя_входного_файла имя_выходного_файла [-t]

Программа принимает в качестве аргументов командной строки:

· имя_входного_файла (обязательный параметр);

· имя_выходного_файла (обязательный параметр);

· -t (НЕобязательный флаг). Если в параметрах программы указан этот флаг, тогда обработка графа производится. Это нужно для тестирования производительности операций чтения из входного файла, парсинга строки в структуры в оперативной памяти.

Формат входного файла:

· Данные записаны построчно и разделены между собой пробелом (т.е. csv-файл с разделителями).

· Строка представляет собой 3 числа:

o № начальной вершины (беззнаковое целое);

o № конечной вершины (беззнаковое целое);

o вес пути (целое со знаком).

· В строке могут быть некорректные данные: символы или слова, не являющиеся числами.

· Количество строк произвольно. Может быть очень большим.

Форматы выходного файла в зависимости от задания:

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

· Набор путей в графе выводится как несколько строк с путями.

Индивидуальное задание: Найти "первый попавшийся путь обхода с возвратами", всех вершин ориентированного графа, начиная из той вершины, из которой можно построить такой путь