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.
Luis Fernando Úbeda Camacho
Apuntes de clase
Sergio Orduz
ProfesorExacto puede utilizar Prim o Kruskal dependiendo cual te quede más fácil aplicar
Wilson Fernando Antury Torres
Algoritmo de kruskal: Encuentra el árbol de expansión mínima, enfocándose en las conexiones.
Dayse Poma
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
Miguel Andres Rendon Reyes
Loco, un profe utilizó el algoritmo de Dijkstra, para encontrar la ruta óptima de evacuación en un Hotel.
Elisa Zamarron Muñoz
al final se corrige el árbol de expansión mínima, ignoren del minuto 5:20 al 6:48.
Sebastian Manassero
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.
Percival Ernesto Amezola Rivera
Me di cuenta por qué parece una cruz básica
VICTORIA HERNÁNDEZ MARTÍNEZ
Supongo que lo hizo para hacer ver qué pueden usarse como herramientas de comprobación del resultado al aplicar uno u otro algoritmo
Julio Anaya
Y el vértice “d”?
Julio Anaya
En el minuto 6:36, se toma tambien el vértice “d” para el costo toal ?
Daniel Fernando Martínez Quintero
se le olvido la d
Juan Nuñez
sólo un detalle mínimo y es que el valor del árbol es 27 porque se le fue el nodo d.
Wilson Fernando Antury Torres
deja vu
Max Andy Diaz Neyra
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:
Alejandro Muñoz
No ha pasado nada señores jajaja
Sara Yaneth Contreras Elías
++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).
Isabella Callejas
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!
Percival Ernesto Amezola Rivera
Erik Ucenik
Reitero la pregunta de un compañero: ¿cómo validaríamos que añadir cierto enlace no generase un ciclo?
Erik Ucenik
Se me ocurre comprobar si los vértices de ese enlace están ya incluídos en nuestro árbol, pero no sé si esto dejaría algún edge-case suelto
Ricardo Torres
En el caso que hubiese decidido seleccionar esta arista, hubiera contado como un ciclo cerrado??
Oriol Fernando Palacios Durand
Sí, se forma una figura cerrada/convexa de vértices ABCFE
Adrian Alberto Casas Lopez
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?
Elisa Zamarron Muñoz
Es indistinto, puede ser cualquiera.
Santiago Vigo
Excelente
Jhins Ledys Cárdenas Pardo
Excelente explicación.
Raul Armas
Según me parece este algoritmo es más eficiente que el de Prim.
Dimas Antonio Mendoza Lozano
Creo que todo depende del escenario en el cual se este desarrollando
Rodrigo Urquizo Yepez
En realidad ambos son eficientes dependiendo del contexto, por ejemplo, si tienes muchas aristas no convendria usar Kruskal en terminos computacionales ya que tendria que iterar vertice por vertice hasta encontrar el de menor coste, en ese caso seria mas eficiente usar Prim.En lo que estaba leyendo Prim es mucho mas rapido cuando tenemos muchas mas aristas que nodos.
