Обход графа: кратчайший путь, BFS и DFS

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 29

Раздел

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

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

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

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

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

   Бинарный поиск Поиск в глубину (DFS) Поиск в ширину (BFS) Сортировка слиянием
2. 2
   Какая структура данных используется в алгоритме BFS для хранения вершин?

   Двоичная куча Очередь Стек Хеш-таблица
3. 3
   Какая структура данных лежит в основе итеративного алгоритма DFS?

   Куча Очередь Словарь Стек