← Назад к списку задач

bfs кратчайший путь невзвешенный

Структуры данных Уровень 2

Описание задачи

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

На вход подается:
* g: Словарь, представляющий граф в виде списка смежности, где ключи – это вершины графа, а значения – списки соседних вершин.
* start: Начальная вершина (узел) для поиска пути.
* goal: Целевая вершина (узел) для поиска пути.

На выходе возвращается:
* Список вершин, представляющий кратчайший путь от начальной вершины start до целевой вершины goal. Если путь не существует, возвращается None.

Режим обучения Готово

Объяснение решения уже подготовлено. Нажмите кнопку, чтобы посмотреть.

Ваше решение

Подсказка (готовое решение)

def bfs_shortest_path(g, start, goal):