Содержание
Цель работы_________________________________________________ 3
Задание к лабораторной работе_________________________________ 3
Порядок выполнения___________________________________________ 6
Содержание отчета___________________________________________ 7
Контрольные вопросы_________________________________________ 7
Литература__________________________________________________ 7
Цель работы
В лабораторной работе необходимо сделать и отладить программу, использующую графы и алгоритмы работы с ними.
Задание
Разработать программу поиска в графе в соответствии с вариантом задания (Табл. 1).
Провести тестирование качества разработанной программы в соответствии с планом тестирования.
Тестовые данные составляются самостоятельно.
Общий алгоритм работы программы:
Чтение входного файла и формирование в памяти графа.
Работа с графом в соответствии с индивидуальном заданием.
Запись результатов в выходной файл.
По окончании работы программа выводит в консоль время работы в миллисекундах.
Требования к входным и выходным данным
Выходные данные. По окончании работы программа выводит 1 беззнаковое целое число, и перевод строки (std::endl или “\n”). Никакой другой текстовой или числовой информации, или единиц измерения не выводится.
Команда запуска программы:
graphsearch.exe имя_входного_файла имя_выходного_файла [-t]
Программа принимает в качестве аргументов командной строки:
· имя_входного_файла (обязательный параметр);
· имя_выходного_файла (обязательный параметр);
· -t (НЕобязательный флаг). Если в параметрах программы указан этот флаг, тогда обработка графа производится. Это нужно для тестирования производительности операций чтения из входного файла, парсинга строки в структуры в оперативной памяти.
Формат входного файла:
· Данные записаны построчно и разделены между собой пробелом (т.е. csv-файл с разделителями).
· Строка представляет собой 3 числа:
o № начальной вершины (беззнаковое целое);
o № конечной вершины (беззнаковое целое);
o вес пути (целое со знаком).
· В строке могут быть некорректные данные: символы или слова, не являющиеся числами.
· Количество строк произвольно. Может быть очень большим.
Форматы выходного файла в зависимости от задания:
· Путь в графе выводится как последовательность номеров вершин, разделенных пробелами, начиная с начальной и заканчивая конечной.
· Набор путей в графе выводится как несколько строк с путями.
Табл. 1
| № Варианта | Задание |
| В ориентированном графе найти путь, проходящий через каждую вершину только один раз. Иначе это называется задача коммивояжера (с ограничением на однократное посещение города). | |
| В ориентированном графе найти все циклы. | |
| В ориентированном взвешенном графе найти подграф. | |
| Найти "первый попавшийся путь обхода с возвратами", всех вершин ориентированного графа, начиная из той вершины, из которой можно построить такой путь | |
| Реализовать поиск в дереве в ширину двумя способами: с помощью использования рекурсии и без использования рекурсии. | |
| Реализовать поиск в дереве (Depth-limited search) | |
| В ориентированном взвешенном графе с отрицательными и положительными весами ребер найти кратчайший путь между двумя вершинами (Bellman--Ford algorithm). | |
| Найти все кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа. | |
| Реализовать поиск в дереве (Iterative deepening depth-first search) | |
| Реализовать поиск в дереве в глубину двумя способами: с помощью использования рекурсии и без использования рекурсии. | |
| В ориентированном взвешенном графе найти путь, проходящий через каждую вершину как минимум один раз. При этом стоимость пути (т.е. сумма всех весов ребер пути) должна быть минимальна. Иначе это называется задача коммивояжера (с ограничением на стоимость пути). | |
| В ориентированном графе найти эйлеров путь, проходящий через каждое ребро графа один раз. | |
| В ориентированном графе найти все циклы, без учета того, что граф ориентированный. | |
| В ориентированном графе найти путь, проходящий через каждую вершину только один раз. Иначе это называется задача коммивояжера (с ограничением на однократное посещение города). | |
| В ориентированном невзвешенном графе найти подграф. | |
| Реализовать поиск подграфа в ориентированном взвешенном графе с отрицательными и положительными весами. | |
| В ориентированном графе найти путь, проходящий через каждую вершину как минимум один раз. При этом длина пути (т.е. количество всех ребер пути без учета их веса) должна быть минимальна. Иначе это называется задача коммивояжера (с ограничением на длину пути). | |
| В неориентированном невзвешенном графе найти подграф. | |
| Реализовать поиск в ориентированном взвешенном графе с неотрицательными весами ребер (Dijkstra's algorithm). | |
| Дан ориентированный взвешенный граф городов и дорог между ними. Дан массив оценок расстояний между каждой парой городов по прямой. Реализовать поиск кратчайшего расстояния между двумя городами с помощью алогритма [A\* (https://en.wikipedia.org/wiki/A*_search_algorithm)]. | |
| Найти кратчайшее расстояние между двумя вершинами во взвешенном ориентированном графе. | |
| Реализовать поиск поддерева в дереве. | |
| Реализовать поиск подграфа в ориентированном взвешенном графе с циклами. | |
| Реализовать поиск в дереве в глубину двумя способами: с помощью использования рекурсии и без использования рекурсии. | |
| В ориентированном взвешенном графе найти путь, проходящий через каждую вершину как минимум один раз. При этом стоимость пути (т.е. сумма всех весов ребер пути) должна быть минимальна. Иначе это называется задача коммивояжера (с ограничением на стоимость пути). | |
| В ориентированном графе найти эйлеров путь, проходящий через каждое ребро графа один раз. | |
| В ориентированном графе найти все циклы, без учета того, что граф ориентированный. | |
| В ориентированном графе найти путь, проходящий через каждую вершину только один раз. Иначе это называется задача коммивояжера (с ограничением на однократное посещение города). | |
| Найти "первый попавшийся путь обхода с возвратами", всех вершин ориентированного графа, начиная из той вершины, из которой можно построить такой путь | |
| Реализовать поиск в дереве в ширину двумя способами: с помощью использования рекурсии и без использования рекурсии. | |
| Реализовать поиск в дереве (Depth-limited search) | |
| В ориентированном взвешенном графе с отрицательными и положительными весами ребер найти кратчайший путь между двумя вершинами (Bellman--Ford algorithm). | |
| Найти все кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа. | |
| Найти кратчайшее расстояние между двумя вершинами во взвешенном ориентированном графе. | |
| Реализовать поиск поддерева в дереве. | |
| Реализовать поиск подграфа в ориентированном взвешенном графе с циклами. | |
| Реализовать поиск в дереве в глубину двумя способами: с помощью использования рекурсии и без использования рекурсии. | |
| В ориентированном взвешенном графе найти путь, проходящий через каждую вершину как минимум один раз. При этом стоимость пути (т.е. сумма всех весов ребер пути) должна быть минимальна. Иначе это называется задача коммивояжера (с ограничением на стоимость пути). | |
| В ориентированном графе найти эйлеров путь, проходящий через каждое ребро графа один раз. | |
| В ориентированном графе найти все циклы, без учета того, что граф ориентированный. |