Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 21

GATE

Рассмотрим следующий график,

Среди следующих последовательностей:

(I) a b e g h f 
(II) a b f e h g
(III) a b f h g e 
(IV) a f g h b e

Каковы глубинные обходы вышеупомянутого графика?
(A) только I, II и IV
(B) только I и IV
(C) только II, III и IV
(D) только I, III и IV

Ответ: (D)
Пояснение: DFS графа

1) Visits a node. 
2) Do following for every unvisited adjacent.
   a) Completely explores all vertices through current 
      adjacent using recursive call to DFS.

Возможна любая DFS, так как мы можем выбирать разные вершины в качестве отправных точек и мы можем выбирать смежные области в разных порядках.

(i) abeghf [Посетите a, изучите все смежные области через b и т. д.]. В этом b соседний е выбирается первым
(iii) abfhge [Посетите a, изучите все смежные области через b и т. д.]. В этом b соседний f выбирается первым
(iv) afghbe [Посетите a, изучите все смежные области через f и т. д.]. В этом соседнем f выбирается первым

(ii) abfehg не может быть ответом, так как e посещается после того, как f [e не является смежным с f, и все смежные с f еще не исследованы]
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2003 | Вопрос 21

0.00 (0%) 0 votes