PUERTA | GATE-IT-2004 | Pregunta 56

Considere el siguiente gráfico no dirigido:
GATE2004-IT_56

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, MI)

Respuesta: (D)
Explicación: A . Falso  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.

B.  Falso  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.

Por lo tanto, la respuesta es D

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/
Prueba de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior

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 *