Considere un grafo no ponderado no dirigido G. Haga un recorrido de G primero en anchura a partir de un Node r. Sean d(r, u) y d(r, v) las longitudes de los caminos más cortos de r a u y v respectivamente, en G. Si se visita u antes que v durante el recorrido primero en anchura, ¿cuál de las siguientes afirmaciones ¿es correcto? (GATE CS 2001)
(A) d(r, u) < d (r, v)
(B) d(r, u) > d(r, v)
(C) d(r, u) <= d ( r, v)
(D) Ninguna de las anteriores
Respuesta: (C)
Explicación: d(r, u) y d(r, v) serán iguales cuando u y v estén al mismo nivel, de lo contrario d(r, u) será menor que d(r, v)
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