Задание № 5271

Студент

Некряч Александр

Задача

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

Состояние

Открыто

Назначено

03.07.2023, 02:14

Обновлено

03.07.2023, 03:14

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

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

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

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

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

Типы данных:

string - string

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

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

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

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

Действия