ISRO | CSRO ISRO 2020 | Pregunta 17

G es un gráfico no dirigido con un conjunto de vértices {v1, v2, v3, v4, v5, v6, v7} y un conjunto de aristas {v1v2, v1v3, v1v4, v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7}. Se realiza una búsqueda en amplitud del gráfico con v1 como Node raíz. ¿Cuál de los siguientes es un borde de árbol?
(A) v2v4
(B) v1v4
(C) v4v5
(D) v3v4

Respuesta: (B)
Explicación: el gráfico dado es,

Ahora, según Breadth First Search o BFS para un gráfico ,

Claramente, v2v4, v3v4 no pueden ser el borde del árbol, mientras que v1v4 y v4v5 pueden ser el borde del árbol. Sucede que v4v5 puede no estar presente en todos los recorridos, pero v1v4 seguramente estará en los recorridos.

La opción (B) es correcta.
Cuestionario de esta pregunta

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *