Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 55

Пусть G = (V, E) простой неориентированный граф, а s определенная вершина в нем, называемая источником. Для x ∈ V пусть d (x) обозначает кратчайшее расстояние в G от s до x. Поиск в ширину (BFS) выполняется, начиная с s. Пусть T будет результирующим BFS-деревом. Если (u, v) является ребром G, которого нет в T, то какой из следующих НЕ МОЖЕТ быть значением d (u) — d (v)?
(А) -1
(Б) 0
(С) 1
(D) 2

Ответ: (D)
Объяснение: Обратите внимание, что данный граф является ненаправленным, поэтому ребро (u, v) также означает, что (v, u) также является ребром.

Поскольку более короткий путь всегда можно получить с помощью ребра (u, v) или (v, u), разница между d (u) и d (v) не может быть больше 1.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 55

0.00 (0%) 0 votes