Considere el siguiente gráfico no dirigido:
Usando el algoritmo de Prim para construir un árbol de expansión mínimo comenzando con el Node A, ¿cuál de las siguientes secuencias de aristas representa un orden posible en el que se agregarían las aristas para construir el árbol de expansión mínimo?
(A) (E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
(B) (A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
(C) (A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
(D) (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
Respuesta: (D)
Explicación: A y B son falsos : la idea detrás del algoritmo de Prim es construir un árbol de expansión, lo que significa que todos los vértices deben estar conectados , pero aquí los vértices están desconectados .
C. Falso. Prim’s es un algoritmo codicioso y, en cada paso, considera todos los bordes que conectan los dos conjuntos y selecciona el borde de peso mínimo de estos bordes. En esta opción, el peso de AB<AD debe recogerse primero.
D. VERDADERO. Representa un orden posible en el que se agregarían los bordes para construir el árbol de expansión mínimo. El algoritmo de Prim también es un algoritmo Greedy . Comienza con un árbol de expansión vacío. La idea es mantener dos conjuntos de vértices. El primer conjunto contiene los vértices ya incluidos en el MST, el otro conjunto contiene los vértices aún no incluidos. En cada paso, considera todos los bordes que conectan los dos conjuntos y selecciona el borde de peso mínimo de estos bordes. Después de seleccionar el borde, mueve el otro extremo del borde al conjunto que contiene MST. Lea más en: https://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
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