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 ordenar_por_costo(const Arista &a, const Arista &b) {
    return a.costo < b.costo;
}

int raiz[10000];
int buscar_raiz(int nodo) {
    if (raiz[nodo] == nodo) return nodo;
    return raiz[nodo] = buscar_raiz(raiz[nodo]);
}

int kruskal() {
    int costo_total = 0;
    for (int i = 1; i <= n; ++i) raiz[i] = i;
    sort(aristas + 1, aristas + m + 1, ordenar_por_costo);
    for (int i = 1; i <= m; ++i) {
        int raiz_origen = buscar_raiz(aristas[i].origen);
        int raiz_destino = buscar_raiz(aristas[i].destino);
        if (raiz_origen == raiz_destino) continue;
        raiz[raiz_origen] = raiz_destino;
        costo_total += aristas[i].costo;
    }
    return costo_total;
}

Algoritmo de Prim

Prim construye el árbol progresivamente desde un vértice inicial, seleccionando en cada paso la arista más barata que conecta un vértice dentro del árbol a uno externo. Utiliza un montículo mínimo para eficiencia, logrando una complejidad de O(m log n).

typedef pair<int int=""> Par;
priority_queue<par vector="">, greater<par>> cola_prioridad;

int prim() {
    int distancia[10000];
    bool visitado[10000] = {false};
    for (int i = 1; i <= n; ++i) distancia[i] = 1e9;
    distancia[1] = 0;
    cola_prioridad.push({0, 1});
    int vertices_agregados = 0, costo_total = 0;

    while (!cola_prioridad.empty()) {
        auto [costo_actual, vertice] = cola_prioridad.top();
        cola_prioridad.pop();
        if (visitado[vertice]) continue;
        visitado[vertice] = true;
        costo_total += costo_actual;
        vertices_agregados++;
        if (vertices_agregados == n) break;

        for (int i = cabeza[vertice]; i != -1; i = siguiente[i]) {
            int vecino = destino[i];
            if (!visitado[vecino] && peso[i] < distancia[vecino]) {
                distancia[vecino] = peso[i];
                cola_prioridad.push({peso[i], vecino});
            }
        }
    }
    return (vertices_agregados < n) ? -1 : costo_total;
}</par></par></int>

Implementación de la lista de adyacencia

Para Prim, se usa una lista de adyacencia enlazada estática para acceder rápidamente a los vecinos.

int contador_aristas = 0;
int cabeza[10000], siguiente[20000], destino[20000], peso[20000];

void agregar_arista(int u, int v, int w) {
    destino[contador_aristas] = v;
    peso[contador_aristas] = w;
    siguiente[contador_aristas] = cabeza[u];
    cabeza[u] = contador_aristas++;
}

Kruskal es más sencillo de implementar con ordenación de aristas, mientras que Prim requiere manejar distancias y un montículo, pero ambos son efectivos para grafos densos y dispersos respectivamente.