A√ļn no tienes acceso a esta clase

Crea una cuenta y contin√ļa viendo este curso

Algoritmo de Kruskal

36/40
Recursos

El algoritmo de Kruskal al igual que el algoritmo de Prim sirve para buscar el árbol de expansión mínimo, la diferencia es que el algoritmo de Kruskal inicia seleccionando la arista de menor valor y después en cada iteración se agrega la arista de menor valor del conjunto disponible.

Aportes 33

Preguntas 2

Ordenar por:

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

Joseph B. Kruskal(1928-2010). Fue un matemático y estadístico estadounidense.
Investigador en el Bell-Labs, en 1956, descubrió un algoritmo para la resolución del problema del árbol recubridor mínimo, el cual es un problema típico de optimizacion combinatoria.

Algoritmo de kruskal: Encuentra el árbol de expansión mínima, enfocándose en las conexiones.

  • 1: Encontramos la conexi√≥n con menor coste.
  • 2: Repetimos la misma iteraci√≥n. buscamos la otra conexi√≥n con menos costo obviando la de la anterior iteraci√≥n.
  • 3: Debemos tener cuidado con no elegir una conexi√≥n que nos cree un ciclo.

Al llegar a este punto te das cuenta de que los grafos estan en todos lados y algoritmos como los que vemos en clases sirven para resolver problemas comunes como es el encontrar la ruta más corta para que tu conexión de internet sea más rápida y cómo funcionan los algoritmos de ciertos programas que usamos a diarios, un curso que vale la pena totalmente tomar

al final se corrige el árbol de expansión mínima, ignoren del minuto 5:20 al 6:48.

Alguien mas se dio cuenta que es el mismo ejemplo de arbol de expansion minima que uso para el Algoritmo de prim? Solo un dato curioso.

Os comparto mi implementación del algoritmo en python:

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

Algoritmo de Kruskal
Es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa).

Y el v√©rtice ‚Äúd‚ÄĚ?

sólo un detalle mínimo y es que el valor del árbol es 27 porque se le fue el nodo d.

deja vu

No ha pasado nada se√Īores jajaja

Una peque√Īa observaci√≥n de la diapositiva: Falt√≥ el nombre del nodo b y cambiar el ‚Äúinicio‚ÄĚ que est√° al final por ‚Äúfin‚ÄĚ.
¬°Muy buen curso!

Mis apuntes:

  • El algoritmo de Kruskal sirve para encontrar el √°rbol de expansi√≥n m√≠nimo.

  • Joseph B. Kruskal(1928-2010). Fue un matem√°tico y estad√≠stico estadounidense.
    Investigador en el Bell-Labs, en 1956, descubrió un algoritmo para la resolución del problema del árbol recubridor mínimo, el cual es un problema típico de optimizacion combinatoria.

  • Pasos del algoritmo:

  1. Selecciona la arista menor.
  2. En cada iteración agregue la arista de menor longitud del conjunto de arcos disponibles.
  3. El algoritmo finaliza cuando todos los vértices están conectados con n-1 arcos.

El algoritmo de Kruskal incia: 1. Seleccionar la arista de menor valor y allí tomar el vértice, 2. En cada iteración agregue la arista de menor longitud del conjunto de arcos disponibles, 3. El algoritmo finaliza cuando todos los vértices están conectados con n-1 arcos.

Me ha gustado mucho esta clase, podemos uso el de kruskal o el de prim para validar uno o el otro.

después del minuto 6:50, se hace la corrección del nodo faltante (d), y dan la solución real del ejemplo … ruta optima de 27.

Excelente explicación.

En el ejemplo que resuelven se observa que la arista con menos ponderaci√≥n es la que va de f a i con un valor=1 pero si en ves de 1 tuviese un valor de 2, esto nos daria tres aristas con valor de 2, ¬Ņen este escenario por cual se comenzaria?

Similitud Algoritmo de Kruskal con Prim. √Ārbol de Expansi√≥n m√≠nimo

Diferencia con el Algoritmo de Kruskal del de Prim. Enfoque sobre las conexiones (la del menor valor)

Al diagramar la soluci√≥n hizo falta agregar la v√©rtice ‚Äėd‚Äô con un coste de 5

Ejercicio pr√°ctico sobre Algoritmo de Kruskal

√Ārbol de expansi√≥n m√≠nima

arbol de expansión mínimo. primero seleccionar una conexión con menor valor

Me sirve mucho para estudiar para el parcial final :V, gracias

Ya arreglaron el error…

Excelente

Algoritmo de Kruskal
Nos permite hallar el árbol de expansión minima, A diferencia del algoritmo de Prim nos centraremos en las conexiones
Pasos:

  • Elegimos la conexi√≥n de m√≠nimo valor
  • Iteramos eligiendo las conexiones de valor m√≠nimo con el cuidado de no generar ciclos
  • El algoritmo termina con todos los nodos conectados con n-1 aristas

Faltó el nodo d.

Seg√ļn me parece este algoritmo es m√°s eficiente que el de Prim.

Revisar en algoritmos la complejidad de cada uno de ellos, al momento de que los nodos y aristas aumenten.

excelente clase