A√ļn no tienes acceso a esta clase

Crea una cuenta y contin√ļa viendo este curso

Algoritmo de Prim

34/40
Recursos

Recordemos que un algoritmo es una serie de pasos que nosotros seguiremos de acuerdo con una lógica.

El algoritmo de Prim nos sirve para conectar todos los vértices a través de un árbol con el mínimo coste. Para calcular el coste total del árbol debemos sumar el valor de todas las aristas conectadas.

El algoritmo de Prim nos indica que este se termina cuando hemos conectado todos los v√©rtices con n-1 aristas, donde n es el n√ļmero de v√©rtices.

Aportes 31

Preguntas 1

Ordenar por:

¬ŅQuieres ver m√°s aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesi√≥n.

Robert C. Prim, nació en 1921, en Estados Unidos, es matemático e ingeniero en sistemas. En los laboratorios Bell, trabajo como director de investigación matemática.
All√≠ desarrollo el conocido Algoritmo de Prim. Con su compa√Īero, Joseph Kruskal, desarrollo dos algoritmos diferentes para encontrar los arboles abarcadores m√≠nimos en un grafo ponderado.

Un poco m√°s y sale una esv√°stica en el √°rbol.

Bienvienida la redundancia, hola clase de arbol de expancion minimo xD

Dejo como aporte el código del algoritmo implementado en python.

https://github.com/ceporro/Algorythms/blob/master/prim_algoryhm.py

Con el algoritmo de Prim es super facil sacar el Arbol de expansion minimo super facil

Algoritmos: Serie de pasos a seguir con una lógica para lograr un objetivo.

Algoritmo prim: encuentra el menor costo de recorrer todos los vértices de un árbol de expansión.

  • 1: escogemos un v√©rtice al azar.
  • 2: escogemos la arista con menor coste.
  • 3: hacemos lo mismo que el paso 2, solo que ya se extienden las opciones con el nuevo v√©rtice.
  • 4: debemos tener cuidado de no crear ciclos, √©stos terminar√≠an el algoritmo.-
  • 5: El algoritmo termina cuando hemos conectado todos los v√©rtices con n-1 aristas, donde n es la cantidad de v√©rtices.

Muy similar al arbol de expasion minimo. De igual manera muy buena explicacion profe!

Algoritmo de prim: coste mínimo de conectar todos los vertices

En lo personal considero que este profesor da unas clases excelentes pero a veces al explicar pierde demasiado tiempo dando ejemplos de conceptos que ya en s√≠ mismos est√°n claros o explicando las cosas de forma distinta, y eso a veces genera m√°s dudas en los alumnos o videos m√°s largos que a la larga generan menor eficiencia en la din√°mica del curso. ūüėĄ

Al momento de escribir código lo usamos para resolver un problema usando la menor cantidad de lineas de código, o usando funciones para hacer del algoritmo algo mas eficiente.

Encontré este articulo donde también se explica y además se implementa en diferentes lenguajes de programación como Java, C#, Python, etc…

Enlace a la p√°gina

chicos un reto natural aquí para todos es que programen esto de manera que probando iniciar en los distintos puntos se logre encontrar la ruta de menor gasto. Seria genial si lo hacen enfocado a distancia entre ciudades para hallar la ruta mas corta de todas las posibles. En mi caso a penas lo tenga lo cargaré en la zona de tutoriales.

Me parece este curso como muy b√°sico o eso es todo lo de matem√°ticas discretas?

Resumen de la clase:

  • Un algoritmo es una serie de pasos los cuales seguiremos de acuerdo a una l√≥gica para conseguir el objetivo.

  • El algoritmo de Prim nos permite encontrar el √°rbol de expansi√≥n m√≠nimo.

  • Este algoritmo sirve para conectar todos los v√©rtices del grafo con el m√≠nimo coste obteniendo.

  • Los pasos son:
    ‚ÄĘ Seleccionamos un v√©rtice cualquiera.
    ‚ÄĘ Selecciona la arista de menor peso conectada al v√©rtice seleccionado.
    ‚ÄĘ En cada iteraci√≥n seleccionamos la arista de menor peso, relacionada con los v√©rtices conectados.
    ‚ÄĘ El algoritmos finaliza cuando todos los v√©rtices est√°n conectados con (n-1) aristas, donde n es el n√ļmero de v√©rtices.
    ‚ÄĘ Importante no se pueden formar ciclos.

En ingeniería de transporte estos algoritmos se usan para asignar rutas de transporte publico

Lo más interesante de este algoritmo, es que siempre nos da la misma figura, no importa dónde comencemos.

El algoritmo de Prim se hace: 1. Seleccionando cualquier vértice al azar, 2. Seleccionar la arista de menor costo relacionado con el vértice seleccionado, 3. Al pasar de vértice, nuevamente hacemos el paso dos. 4. El algoritmo termina cuando la conexión total de las aristas sea n-1, osea vértices menos 1.

El algoritmo de Prim y otros, están enfocados en siempre encontrar el arbol de expansión mínimo.

Calculos completos. Graficación

Fin del algoritmo: Vertices = n-1 aristas

Ejemplo pr√°ctico de Algoritmo de Prim

Excelente.

Arbol de expansión mínimo, excelente

Para programar ésto es necesario usar una matriz de incidencia.

Muy interesante

Bien. Una mejor manera de desarrollar el árbol de expansión mínimo.

Excelente explicación!

Algoritmo de Prim
Con este algoritmo generamos el árbol de expansión mínimo y por tanto el coste mínimo en el grafo.
Procedimiento

  • Elegimos un nodo al azar
  • Elegimos la conexi√≥n de valor m√≠nimo
  • Iteramos eligiendo la conexi√≥n de valor m√≠nimo hasta conectar todos los nodos, cuidando de no conectar un nodo ya incluido (no crear ciclos)

Nota:
El algoritmo termina con todos los nodos conectados a través de n-1 aristas.

Interesante clase.

ALGORITMO DE PRIM
Es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

El algoritmo fue dise√Īado en 1930 por el matem√°tico Vojtech Jarnik y luego de manera independiente por el cient√≠fico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta raz√≥n, el algoritmo es tambi√©n conocido como algoritmo DJP o algoritmo de Jarnik.