BFS и DFS: эффективность обходов графа

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 15

Раздел

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

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

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

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

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

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

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

   \(O(E \log V)\) \(O(V \cdot E)\) \(O(V+E)\) \(O(V^{2})\)