Студент

Бородин Артём

Задача

Пересдача № 2 - Графы

Состояние

Открыто

Назначено

10.09.2021, 09:37

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

Входные данные

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

Текстовый файл содержащий набор ребер графа:

<вершина N>-<вершина K>

Типы данных:

string - string

Постановка задачи

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

Обязательные требования:

1. Для обхода графа нельзя использовать рекурсию.
2. Код должен быть модульным и переиспользуемым.
3. Построение графа и обход графа не должны зависеть от источника входных данных, т.е. от потока.
4. По возможности необходимо использовать STL алгоритмы.