Algoritmos | Árbol de expansión mínimo del gráfico | Pregunta 6

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?
gate_2006

(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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *