Алгоритм поиска в ширину (BFS)

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 24

Раздел

Алгоритмы на графах (Python)

Цели обучения

• 11.2.2.2анализировать эффективность алгоритмов BFS и DFS и выбирать оптимальный метод

Примеры вопросов

1. 1
   Какая структура данных используется в алгоритме BFS?

   Куча Очередь Связный список Стек
2. 2
   Какова временная сложность BFS для графа с V вершинами и E рёбрами?

   \(O(E \log V)\) \(O(V \cdot E)\) \(O(V+E)\) \(O(V^{2})\)
3. 3
   Что находит BFS в невзвешенном графе?

   Все пути между двумя вершинами Длиннейший путь по числу рёбер Кратчайший путь по числу рёбер Путь с минимальной суммой весов