Friki Work

La meta de un árbol de expansión mínima (MST, por sus siglas en inglés) es encontrar un subgrafo conexo de un grafo no dirigido con n vértices y n-1 aristas, tal que la suma de los pesos de las aristas sea la menor posible. Algoritmo de Kruskal Este algoritmo es eficiente cuando el grafo tiene relativamente pocas aristas. **Principio:**El alogr ...

Algoritmo de Kruskal Este método ordena todas las aristas por peso asecndente y las añade al árbol siempre que no generen ciclos, utilizando una estructura de Union-Find para gestionar componentes conexas. La complejidad temporal es O(m log m) debido a la ordenación. struct Arista { int origen, destino, costo; } aristas[10000]; bool ordena ...