BFS и DFS: сравнение эффективности

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 16

Раздел

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

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

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

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

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

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

   очередь приоритетная очередь стек хеш-таблица
3. 3
   Какая структура данных лежит в основе итеративной версии DFS?

   двоичная куча очередь связный список стек