Поиск на графах: BFS, DFS, Дейкстра

Тема по КТП

Класс

10 класс

Предмет

Информатика

Четверть

2

Урок

№ 18

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

• 10.5.1.5реализовывать алгоритмы поиска на графах для решения практических задач

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

1. 1
   Какая структура данных используется в алгоритме поиска в ширину (BFS)?

   Двоичная куча Очередь Стек Хеш-таблица
2. 2
   Что находит алгоритм Дейкстры в графе с неотрицательными весами рёбер?

   Все циклы, существующие в графе Кратчайшие расстояния от выбранной вершины до всех остальных Минимальное остовное дерево всего графа Порядок вершин для топологической сортировки
3. 3
   BFS запущен из вершины 1. Рёбра графа: 1—2, 1—3, 2—4, 4—5. На каком расстоянии от вершины 1 окажется вершина 5?

   2 3 4 5