Обход графа: прикладная задача

Тема по КТП

Класс

11 класс

Предмет

Информатика

Четверть

2

Урок

№ 27

Раздел

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

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

• 11.2.2.1использовать алгоритмы обхода графов для нахождения кратчайшего пути в прикладных задачах
• 11.2.2.2анализировать эффективность алгоритмов BFS и DFS и выбирать оптимальный метод

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

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

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

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

   очередь приоритетная очередь стек хеш-таблица