Рубрики

ВОРОТА | Gate IT 2007 | Вопрос 24

Поиск в глубину выполняется на ориентированном ациклическом графе. Пусть d [u] обозначает время, когда вершина u посещается впервые, а f [u] время, когда dfs вызывает вершину u. Какое из следующих утверждений всегда верно для всех ребер (u, v) в графе?
(A) d [u] (B) d [u] (C) f [u] (D) f [u]> f [v]

Ответ: (D)
Объяснение:
Запуск DFS на узле V
1] Визит (V) -> DFS (X) -> Визит (X) -> DFS (U) -> Визит (U) -> Возврат (X) -> Возврат (V)
Следовательно: d [U]> d [V], d [U] Но порядок посещения прямо противоположен порядку завершения.
Следовательно, f [U]> f [V]

Тест на этот вопрос

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

ВОРОТА | Gate IT 2007 | Вопрос 24

0.00 (0%) 0 votes