Sea G = (V, E) un grafo simple no dirigido, y s un vértice particular llamado fuente. Para x ∈ V, sea d(x) la distancia más corta en G de s a x. Se realiza una búsqueda en amplitud (BFS) a partir de s. Sea T el árbol BFS resultante. Si (u, v) es una arista de G que no está en T, ¿cuál de los siguientes NO PUEDE ser el valor de d(u) – d(v)?
(A) -1
(B) 0
(C) 1
(D) 2
Respuesta: (D)
Explicación: Tenga en cuenta que el gráfico dado no está dirigido, por lo que un borde (u, v) también significa que (v, u) también es un borde.
Dado que siempre se puede obtener un camino más corto usando el borde (u, v) o (v, u), la diferencia entre d(u) y d(v) no puede ser más de 1.
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