El Algoritmo de Prim se usa para obtener árboles de recubrimiento mínimo y cómo su nombre indica fue propuesto en el año 1957 por Robert C. Prim
Antes de meternos de lleno con él vamos con un poco de historia. Este algoritmo fue propuesto en 1930 por el matemático Vojteck Jarník que fue el primero que lo propuso, unos años después en 1957 fue nuevamente propuesto por Rober C. Prim y finalmente fue redescubierto en 1959 por Edsger Dijkstra
Cómo hemos dicho este algoritmo se usa para obtener árboles de recubrimiento mínimo en un grafo.
El funcionamiento es el
siguiente: (voy a intentar explicarlo con palabras de andar por casa a ver si así se entiende mejor)
Partiendo de un nodo del grafo examinamos todas sus aristas, es decir, todos los caminos posibles que tenemos y elegimos el más corto, desde el siguiente nodo tendremos otros caminos posibles y también nos quedarán los caminos posibles que teníamos desde el primer nodo y lo que tenemos que hacer es elegir el más corto, así sucesivamente hasta que hemos llegado a todos los nodos.
He hecho un pequeño vídeo explicativo con unas imágenes a ver si así se entiende mejor, en azul los nodos que ya forman parte de la solución, en verde las aristas o caminos posibles, en azul las que ya forman parte de la solución y en gris las que ya no pueden formar parte de la solución porque ya hay otros caminos para llegar a esos nodos:
Segundo paso:
Tercer paso:
Cuarto paso:
Quinto paso:
Sexto paso:
Séptimo paso:
Octavo paso, árbol de recubrimiento mínimo:
Espero que os ayude y os sirva. Cualquier cosa no dudéis en ponerla en los comentarios.
Antes de meternos de lleno con él vamos con un poco de historia. Este algoritmo fue propuesto en 1930 por el matemático Vojteck Jarník que fue el primero que lo propuso, unos años después en 1957 fue nuevamente propuesto por Rober C. Prim y finalmente fue redescubierto en 1959 por Edsger Dijkstra
Cómo hemos dicho este algoritmo se usa para obtener árboles de recubrimiento mínimo en un grafo.
El funcionamiento es el
siguiente: (voy a intentar explicarlo con palabras de andar por casa a ver si así se entiende mejor)
Partiendo de un nodo del grafo examinamos todas sus aristas, es decir, todos los caminos posibles que tenemos y elegimos el más corto, desde el siguiente nodo tendremos otros caminos posibles y también nos quedarán los caminos posibles que teníamos desde el primer nodo y lo que tenemos que hacer es elegir el más corto, así sucesivamente hasta que hemos llegado a todos los nodos.
He hecho un pequeño vídeo explicativo con unas imágenes a ver si así se entiende mejor, en azul los nodos que ya forman parte de la solución, en verde las aristas o caminos posibles, en azul las que ya forman parte de la solución y en gris las que ya no pueden formar parte de la solución porque ya hay otros caminos para llegar a esos nodos:
Cada imagen tiene una pequeña explicación para que se entienda mejor.
Os dejo las imágenes que he utilizado para hacer el vídeo por si os pudieran servir.
Primer paso:
 |
| Árbol de recubrimiento mínimo con el algoritmo de Prim |
Segundo paso:
 |
| Árbol de recubrimiento mínimo con el algoritmo de Prim |
 |
| Árbol de recubrimiento mínimo con el algoritmo de Prim |
Cuarto paso:
 |
| Árbol de recubrimiento mínimo con el algoritmo de Prim |
Quinto paso:
 |
| Árbol de recubrimiento mínimo con el algoritmo de Prim |
Sexto paso:
 |
| Árbol de recubrimiento mínimo con el algoritmo de Prim |
Séptimo paso:
 |
| Árbol de recubrimiento mínimo con el algoritmo de Prim |
Octavo paso, árbol de recubrimiento mínimo:
 |
| Árbol de recubrimiento mínimo con el algoritmo de Prim |
Espero que os ayude y os sirva. Cualquier cosa no dudéis en ponerla en los comentarios.
gracias wey me sirvio de mucho
ResponderEliminargracias a ti por visitarnos ;)
Eliminar