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