Обход графа: кратчайший путь на практике

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 28

Раздел

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

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

• 11.2.2.1использовать алгоритмы обхода графов для нахождения кратчайшего пути в прикладных задачах
• 11.2.2.2анализировать эффективность алгоритмов BFS и DFS и выбирать оптимальный метод

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

1. 1
   Какой алгоритм обхода графа гарантирует нахождение кратчайшего пути по числу рёбер в невзвешенном графе?

   BFS (поиск в ширину) DFS (поиск в глубину) Алгоритм Прима Топологическая сортировка
2. 2
   Какова временная сложность BFS и DFS при обходе графа с V вершинами и E рёбрами?

   \(O(E^{2})\) \(O(V + E)\) \(O(V \cdot E)\) \(O(V^{2})\) для любого графа
3. 3
   Какая структура данных используется в алгоритме BFS для хранения вершин, ожидающих обработки?

   Куча (приоритетная очередь) Очередь Стек Хеш-таблица