Considere el siguiente gráfico: ¿Cuál de los siguientes NO es la secuencia de aristas agregadas al árbol de expansión mínimo usando el algoritmo de Kruskal?
(A) (b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
(B) (b,e)(e,f)(a,c) )(f,g)(b,c)(c,d)
(C) (b,e)(a,c)(e,f)(b,c)(f,g)(c,d)
( D) (b,e)(e,f)(b,c)(a,c)(f,g)(c,d)
Respuesta: (D)
Explicación: En la secuencia (b, e) (e, f) (b, c) (a, c) (f, g) (c, d) dada la opción D, el borde (a, c) del peso 4 viene después de (b, c) del peso 3.
En el algoritmo de árbol de expansión mínimo de Kruskal , primero ordenamos todos los bordes, luego consideramos los bordes en orden ordenado, por lo que un borde de mayor peso no puede venir antes que un borde de menor peso.
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