Алгоритм поиска в глубину (DFS)

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 25

Раздел

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

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

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

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

1. 1
   Какой структуре данных соответствует обход графа в глубину (DFS)?

   Дек Куча Очередь Стек
2. 2
   Какова временная сложность DFS для графа с V вершинами и E рёбрами при списке смежности?

   \(O(E \log V)\) \(O(V \cdot E)\) \(O(V+E)\) \(O(V^{2})\)
3. 3
   Какой алгоритм обхода графа использует очередь?

   Алгоритм Краскала Бинарный поиск Поиск в глубину Поиск в ширину