Условие:
Граф задаёт систему связанных между собой объектов. Каждая вершина графа обозначает некоторый пункт, а каждое ребро показывает, что из одного пункта можно перейти в другой.
Необходимо по заданному графу и двум вершинам определить путь от начальной вершины до конечной двумя способами.
Сначала требуется найти любой путь с помощью обхода в глубину. Такой путь зависит от порядка перебора соседей и не обязан быть кратчайшим. Затем требуется найти кратчайший путь с помощью обхода в ширину. Если путь существует, функция должна вернуть список вершин, через которые проходит маршрут от начальной вершины до конечной. Если пути не существует, функция должна вернуть None.
Граф хранится в виде словаря, где ключом является вершина, а значением — список соседних вершин. Начальная и конечная вершины также задаются отдельно.
