Cursos Empresas Blog Live Conf Eventos Precios

0:0011:01

Recursos

Resumen

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.

Algoritmo de Prim: Árbol de Expansión Mínimo en Grafos

Curso de Matemáticas Discretas

Clase 34 de 40

Clase 34 / 40

Comentarios (35)35 comentarios

Luis Fernando Úbeda Camacho

Hace 8 años

Apuntes de clase

Un algoritmo es una serie de pasos, que seguimos de acuerdo a una lógica y si seguimos los pasos consecutivamente lograremos el objetivo.
El algoritmo de Prim lo que nos permite es encontrar el árbol de expansión mínimo, obtendremos el coste mínimo de conectar todos los nodos.
Importante no se pueden formar ciclos.

Secuencia del algoritmo de Prim

Seleccionamos un vértice cualquiera.
Seleccionamos la conexión de menor peso conectada al vértice.
En cada iteración seleccionamos la arista de menor peso, relacionada con los vértices conectados.
El algoritmo finaliza cuando todos los vértices están conectados con (n-1) aristas, por ejemplo si tenemos 9 vértices, tendremos 8 conexiones.

Sergio Orduz

Profesor

Genial! ¿Cúal de tus algortimos ha sido el favorito?

Ahora mismo no sabría decirte, creo que cuando los aplique en el curso de algoritmo sabre decantarme por alguno y el de flujo máximo me pareció el mas complejo.

Irving Ariel Escamilla Jacobo

Hace 7 años

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.

Miguel Andres Rendon Reyes

Hace 5 años

Todo tiene un poco màs de sentido xD

Madison Eduardo Herrera Carrión

Hace 4 años

Muchas gracias por el aporte colega :)

Jordi Santamaría Portolés

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

Wilson Fernando Antury Torres

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.

Jose Ignacio Pomero

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

Dimas Antonio Mendoza Lozano

Hace 6 años

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

Julio Alfredo Machado Olivo

si jaja, queda bien redudante el arbol de expresion minimo una vez que conoces el algoritmo de prim.

César Andrés Santana Gereda

Este curso parece muy básico, o eso es todo lo de matemáticas discretas?

Juan José López Torres

Se toman algunos puntos, hay varios cursos de matemáticas.

Orlando castellanos

si vienes de una carrera de ingenieria o fisico matematico diria que si esta basico pero para muchos que estan decidiendo cambiar de carrera, vienen de otras ramas puede que incluso su educacion fue mala o ya olvidaron todo, pues se da lo basico para empezar a entrar en el mundo de las ciencias, eso o quiza seas un genio ,pero en general los cursos de matematicas de platzi a mi criterio parecen un enorme formulazo, te lo dan todo desarrollado y lo mas sencillo posible para que entiendas lo de lo que se habla en otros cursos de programacion o data sicience

Jose Fernando Jaramillo Boon

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

Christian Sanclemente

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.

johan Stever Rodriguez Molina

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.

Diego Cesar Lerma Torres

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. :D

Sara Yaneth Contreras Elías

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

Carlos Bautista Ardila

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.

Max Andy Diaz Neyra

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.

EDWIN ALEXANDER PARRA GOMEZ

Hace 9 meses

good explication

Ricardo Posada

Hace 3 años

como lo programarias en python?

Catriel Perez

DUDA: es menor costo del vertice o del camino total? porque de E + B = 7 en vez de E + A + B = 8. y lo mismo pasa en E + F + C = 7 en vez de E + A + B + C = 11

Milton Martinez

en realidad no es el costo de llegar con menor cantidad a los puntos, sino el recorrido de todos los puntos con lo mínimo.

Arturo Barrios

Ejemplo práctico de Algoritmo de Prim

Calculos completos. Graficación

Recursos

Resumen

Algoritmo de Prim: Árbol de Expansión Mínimo en Grafos

Progreso del curso

Introducción al curso

Lógica

Teoría de conjuntos

Teoría de grafos

Árboles

Algoritmos

Conclusiones