Algoritmo de Prim

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.

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

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!

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

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

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.

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.

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. 😄

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.

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

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

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.

Ejemplo práctico de Algoritmo de Prim

Calculos completos. Graficación

Fin del algoritmo: Vertices = n-1 aristas

Muy interesante

Excelente.

Excelente explicación!

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

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.

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.

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

Arbol de expansión mínimo, excelente

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

Interesante clase.