Рубрики

ВОРОТА | GATE-CS-2000 | Вопрос 49

Пусть G неориентированный граф. Рассмотрим прохождение в глубину G, и пусть T будет результирующим деревом поиска в глубину. Пусть u будет вершиной в G, и пусть v будет первой новой (не посещенной) вершиной, посещенной после посещения u в обходе. Какое из следующих утверждений всегда верно?
(A) {u, v} должно быть ребром в G, а u является потомком v в T
(B) {u, v} должно быть ребром в G, а v является потомком u в T
(C) Если {u, v} не является ребром в G, то u является листом в T
(D) Если {u, v} не является ребром в G, то u и v должны иметь одного и того же родителя в T

Ответ: (с)
Объяснение:

In DFS, if '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 после посещения узла мы сначала возвращаемся для всех непосещенных детей. Если нет не посещенных детей (это лист), то контроль возвращается к родителю и родителю, а затем посещает следующих непосещенных детей.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2000 | Вопрос 49

0.00 (0%) 0 votes