Considere el siguiente gráfico: ¿Cuál de los siguientes no puede ser la secuencia de aristas agregadas, en ese orden, a un árbol de expansión mínimo usando el algoritmo de Kruskal?
(A) (a—b),(d—f),(b—f),(d—c),(d—e)
(B) (a—b),(d—f),(d— c),(b—f),(d—e)
(C) (d—f),(a—b),(d—c),(b—f),(d—e)
(D) ( d—f),(a—b),(b—f),(d—e),(d—c)
Respuesta: (D)
Explicación: La arista (de) no puede ser considerada antes de (dc) en el mínimo de Kruskal algoritmo de árbol de expansión porque el algoritmo de Kruskal selecciona el borde con el peso mínimo del conjunto actual de bordes en cada paso.
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