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 alogritmo ordena todas las aristas del grafo por peso de forma ascendente. Luego, itera sobre las aristas ordenadas, agregando una arista al MST si esta no forma un ciclo con las aristas ya seleccionadas. La estructura de datos de Union-Find (conjuntos disjuntos) se utiliza para detectar eficientemente la formación de ciclos.

Implementación:

#include <iostream>
#include <vector>
#include <algorithm>

struct Edge {
    int u, v, weight;
};

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

struct DSU {
    std::vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
};

int kruskalMST(int n, std::vector<Edge>& edges) {
    std::sort(edges.begin(), edges.end(), compareEdges);

    DSU dsu(n);
    int mstWeight = 0;
    int edgesCount = 0;

    for (const auto& edge : edges) {
        if (dsu.find(edge.u) != dsu.find(edge.v)) {
            dsu.unite(edge.u, edge.v);
            mstWeight += edge.weight;
            edgesCount++;
            if (edgesCount == n - 1) {
                break;
            }
        }
    }

    if (edgesCount == n - 1) {
        return mstWeight;
    } else {
        return -1; // Indicates no MST possible
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    }

    int result = kruskalMST(n, edges);
    if (result == -1) {
        std::cout << "impossible" << std::endl;
    } else {
        std::cout << result << std::endl;
    }

    return 0;
}

Algoritom de Prim

Este algoritmo es más adecuado para grafos densos (con muchas aristas) y puede ser ineficiente si m log m excede el tiempo límite.

**Principio:**Similar al algoritmo de Dijkstra, Prim's construye el MST gradualmente. Comienza con un vértice arbitrario y, en cada paso, agrega la arista de menor peso que conecta un vértice en el árbol actual a un vérttice fuera del árbol. Se mantiene un registro de la distancia mínima de cada vértice no incluido al árbol.

Implementación:

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

const int INF = std::numeric_limits<int>::max();

int primMST(int n, const std::vector<std::vector<std::pair<int, int>>>& adj) {
    std::vector<int> minDist(n + 1, INF);
    std::vector<bool> inMST(n + 1, false);
    int mstWeight = 0;
    int verticesInMST = 0;

    minDist[1] = 0; // Start with vertex 1

    for (int count = 0; count < n; ++count) {
        int u = -1;
        int minVal = INF;

        // Find the vertex with the minimum distance value, from the set of vertices not yet included in MST
        for (int v = 1; v <= n; ++v) {
            if (!inMST[v] && minDist[v] < minVal) {
                minVal = minDist[v];
                u = v;
            }
        }

        // If no vertex can be added, graph is not connected
        if (u == -1) {
            return -1; // Indicates no MST possible
        }

        inMST[u] = true;
        mstWeight += minDist[u]; // Add the weight of the edge connecting u to MST
        verticesInMST++;

        // Update dist value of the adjacent vertices of the picked vertex.
        // Consider only those vertices not yet included in MST
        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (!inMST[v] && weight < minDist[v]) {
                minDist[v] = weight;
            }
        }
    }

    return mstWeight;
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int result = primMST(n, adj);
    if (result == -1) {
        std::cout << "impossible" << std::endl;
    } else {
        std::cout << result << std::endl;
    }

    return 0;
}