Поиск в глубину (DFS)

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 26

Раздел

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

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

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

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

1. 1
   Какая структура данных лежит в основе итеративной реализации DFS?

   Двоичное дерево Очередь Стек Хеш-таблица
2. 2
   Чем стратегия DFS отличается от BFS?

   Всегда идёт по возрастанию весов Идёт вглубь, затем возвращается Идёт по уровням от старта Обходит только листья дерева
3. 3
   Временная сложность DFS для графа с V вершинами и E рёбрами (список смежности)?

   O(E log V) O(V + E) O(V · E) O(V²)