PUERTA | Puerta TI 2008 | Pregunta 43

Para el gráfico ponderado no dirigido que se muestra a continuación, ¿cuál de las siguientes secuencias de aristas representa una ejecución correcta del algoritmo de Prim para construir un árbol de expansión mínimo? (A) (a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h) (B) (c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i) (C) (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i) (D) (h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e) Respuesta: (C) Explicación: En el algoritmo prims comenzamos con cualquier Node y seguimos explorando los vecinos de costo mínimo de los Nodes ya cubiertos. Cuestionario de esta pregunta