- Какая структура данных лежит в основе алгоритма поиска в ширину (BFS)?
A) стек B) очередь C) двоичная куча D) хеш-таблица
- Что гарантированно находит поиск в ширину в невзвешенном графе при запуске из стартовой вершины s?
A) кратчайшие пути от s до всех достижимых вершин по числу рёбер B) путь с минимальной суммой весов рёбер C) все простые циклы графа D) гамильтонов цикл наименьшей длины
- Дан неориентированный граф с вершинами 1–6 и рёбрами: 1–2, 1–3, 2–4, 3–5, 4–5, 5–6. Поиск в ширину запущен из вершины 1. Чему равно кратчайшее расстояние (в числе рёбер) от вершины 1 до вершины 6?
A) 2 B) 3 C) 4 D) 5
- Какова временная сложность BFS при хранении графа в виде списков смежности? (V — число вершин, E — число рёбер)
A) O(V²) B) O(E log V) C) O(V + E) D) O(2^V)
- Пусть BFS запущен из вершины s, а d(v) — число рёбер в кратчайшем пути из s в v. Какое утверждение верно для любого ребра (u, v) неориентированного графа?
A) |d(u) − d(v)| ≤ 1 B) d(u) = d(v) для любого ребра C) |d(u) − d(v)| может быть сколь угодно большим D) d(u) + d(v) всегда чётно
Ответы
- B — BFS использует очередь (FIFO).
- A — в невзвешенном графе BFS даёт кратчайшие пути по числу рёбер.
- B — путь 1–3–5–6 содержит 3 ребра.
- C — каждая вершина и каждое ребро просматриваются ограниченное число раз: O(V + E).
- A — при обходе в ширину концы любого ребра лежат на одном уровне или на соседних.