Обход графа: BFS и DFS

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 14

Раздел

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

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

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

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

1. 1
   Какая структура данных лежит в основе BFS и реализуется в Python через collections.deque?

   Бинарная куча Очередь Стек Хеш-таблица
2. 2
   Какая структура данных используется в нерекурсивной реализации DFS?

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

   BFS DFS Алгоритм Прима Топологическая сортировка