Please enable JavaScript.
Coggle requires JavaScript to display documents.
ACTIVIDAD - Coggle Diagram
ACTIVIDAD
Algoritmo de Prim
Definición
-
Funciona en grafos conectados, ponderados y no dirigidos
-
-
-
Pasos del algoritmo
- Seleccionar un nodo inicial
- Agregar todas las aristas que lo conectan con otros nodos
- Elegir la arista de menor peso que conecte a un nodo no visitado
- Repetir hasta visitar todos los nodos
-
Ejemplo práctico
Grafo con 5 nodos: A, B, C, D, E
-
Paso a paso
-
- Aristas posibles: A-B (2), A-C (3) → elegir A-B
- Nuevas aristas: B-C (1), B-D (4) → elegir B-C
- Nuevas aristas: C-D (5), C-E (6) → elegir B-D
- Nuevas aristas: D-E (7) → elegir C-E
Árbol resultante
Aristas: A-B (2), B-C (1), B-D (4), C-E (6)
-
-