Рубрики

Алгоритмы | Граф Обходы | Вопрос 12

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

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

(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

Ответ: (Д)
Объяснение: Мы можем проверить все DFS на наличие следующих свойств.

In DFS, if a vertex 'v' is visited
after 'u', then one of the following is true.
1) (u, v) is an edge.
     u
   /   \
  v     w
 /     / \
x     y   z

2) 'u' is a leaf node.
     w
   /   \
  x     v
 /     / \
u     y   z

В DFS после посещения узла мы сначала возвращаемся для всех непосещенных детей. Если нет не посещенных детей (это лист), то контроль возвращается к родителю и родителю, а затем посещает следующих непосещенных детей.
Тест на этот вопрос

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

Алгоритмы | Граф Обходы | Вопрос 12

0.00 (0%) 0 votes