Minimum Spanning Tree

Un problema recurrente en teoría de grafos es el de hallar el mínimo árbol generador de un grafo ponderado y conexo. Recordemos que un árbol es un grafo conexo y acíclico mientras que un grafo generador es un grafo que contiene los mismos vértices que el original y cuyo conjunto de aristas es un subconjunto del original, en otras palabras es el grafo que resulta de extraer alguna (o ninguna) artista de otro. Así pues, dado un grafo conexo y ponderado, nuestro objetivo es seleccionar un conjunto de las aristas de modo que la suma de sus pesos sea mínima y que el grafo resultante sea conexo y acíclico. Para ello hay dos algoritmos muy conocidos: 

Prim

El algoritmo de Prim es muy parecido al de Dijkstra, así que es recomendable leerlo antes de seguir con este.

Este algoritmo consiste en empezar por un vértice e ir añadiendo vértices al conjunto de modo que a cada paso se coja la arista de menor peso. Utilizando la misma terminología que en la explicación de Dijkstra: consideramos un subgrafo F del grafo original G inicialmente formado por un nodo cualquiera. Consideramos todos los nodos a los que podemos llegar desde F, vamos al que esté a distancia mínima de F y lo añadimos; repetimos el proceso hasta haber añadido todos los vértices de G. Veamos un ejemplo sobre el grafo siguiente:

 

Utilizaremos el algoritmo de Prim para obtener el mínimo árbol generador, empezando desde el nodo 1:

Vemos que el mínimo árbol generador del grafo original tiene un coste de 8.

Observaciones:

• El árbol final puede variar dependiendo de cuál sea el nodo desde el que empezamos, pero no su coste.
• El algoritmo también es válido cuando hay pesos negativos.
• La complejidad del algoritmo es de $\mathcal{O}(|E|  \log(|V|))$ 

A nivel de código es prácticamente idéntico al de Dijkstra, salvo que empezamos en cualquier nodo y acabamos tras visitarlos todos.

// Dados un grafo G, sus pesos W y el número de nodos n devuelve el coste del árbol mínimo
// generador usando el algoritmo de Prim
int Prim (vvi& G, vvi& W, int n){
    vector <bool> vis(n, false); //nodos visitados, inicialmente ninguno
    priority_queue <ii> Q; //cola de prioridad de parejas de enteros (-distancia del nodo a F, nodo)
    Q.push({-0,0}); //introducimos un nodo cualquiera (a distancia 0 de él mismo)
    int answer = 0; 

    while (not Q.empty()){
        ii arc = Q.top() //arco con menor peso desde F hasta G\F 
        Q.pop(); //lo quitamos de la cola

        int v = arc.second; //vértice de Q a menor distancia de F
        int p = -arc.first; //distancia entre F y v

        if (not vis[v]){ //si no lo hemos visitado
            vis[v] = true;
            answer += p;

            for (int i = 0; i < G[v].size(); ++i){ //miramos sus vecinos
                int u = G[v][i];
                int w = W[v][i];

                Q.push({-w, u}); // añadimos los vecinos conectados con u
            }
        }   
    }

    return answer; // devolvemos el coste
}

Observación: Al igual que en el caso de Dijkstra se puede hacer más eficiente si solo añadimos a la cola los nodos no visitados.

Kruskal

Este algoritmo consiste en ir cogiendo las aristas de menor a mayor peso y añadirlas a no ser que formen un ciclo con las aristas que ya han sido añadidas. Veamos un ejemplo:

Utilizaremos el algoritmo de Kruskal para obtener el mínimo árbol generador. Vamos visitando los arcos de menor a mayor peso:

1. Consideramos el arco 3 - 4, no forma ciclo, por lo tanto lo cogemos.

2. Consideramos el arco 1 - 2, no forma ciclo, por lo tanto lo cogemos.

3. Consideramos el arco 2 - 4, no forma ciclo, por lo tanto lo cogemos.

4. Consideramos el arco 5 - 6, no forma ciclo, por lo tanto lo cogemos.

5. Consideramos el arco 1 - 3, de cogerlo formaría un ciclo (1-2-4-3-1) por lo que no lo cogemos.

6. Consideramos el arco 1 - 6, no forma ciclo, por lo tanto lo cogemos.

Vemos que el mínimo árbol generador del grafo original tiene un coste de 12.

Observaciones:

• Como vemos en el ejemplo, no es suficiente con visitar todos los nodos, es necesario tomar exactamente n - 1 aristas, siendo n el número de nodos.
• El algoritmo también es válido cuando hay pesos negativos.
• La complejidad del algoritmo es de $\mathcal{O}(|E| \log(|E|))$ 

Para entender el código es necesario leer primero el capítulo de la estructura de unión-busqueda para conjuntos disjuntos del apartado de estructuras de datos.

A medida que vamos cogiendo aristas se van formando componentes conexas, nos interesa saber de un modo sencillo y eficiente si dos vértices pertenecen a la misma componente conexa así como juntar componentes conexas. Para ello utilizaremos la estructura de unión-búsqueda para conjuntos distintos. Asociamos un nodo representante para cada componente conexa, de modo que todos los nodos de la misma componente conexa tienen como representante ese nodo. Inicialmente tenemos n componentes conexas (cada uno de los nodos) y su nodo representante es el propio nodo. Cada vez que escojamos una arista que conecte dos componentes conexas pondremos como representante del representante de una de las componentes al otro representante, de modo que todos los nodos de la nueva componente conexa tendrán el mismo nodo representante. Si dos nodos tienen el mismo representante son de la misma componente conexa y, por ende, no podemos coger un arco que los una, pues se formaría un ciclo.

A continuación figura una posible implementación del Algoritmo de Kruskal

vi p; // Vector del representante de cada nodo (p[i] es el representante de i)

// Dado un nodo nos devuelve su representante y a la vez hacemos una compresión de caminos
int findSet(int i) {
    if (p[i] != i) p[i] = findSet(p[i]); //buscamos el representante de la componente
    return p[i];
}

// Dados el número de nodos del grafo (n), y el conjunto de aristas (edges) donde edge[i] =
// {peso del arco, nodo, nodo}, devuelve el coste del mínimo árbol generador.
int Kruskal(int n, vector <vi>& edges) {
    sort(edges.begin(), edges.end()); // Ordenamos de menor a mayor los arcos según su peso

    p = vi(n);
    for (int i = 0; i < n; ++i) p[i] = i; // el representante de cada nodo es él mismo
    int answer = 0; // variable donde acumulamos los pesos de los arcos que cogemos

    for (int i = 0; i < edges.size(); ++i){
        vi arc = edges[i]; 

        int u = arc[2];
        int v = arc[1];
        int w = arc[0];

        int pu = findSet(u); // representante del nodo u
        int pv = findSet(v); // representante del nodo v

        if (pu != pv){ // si no tienen el mismo representante, u y v forman parte de
                       // componentes conexas distintas, por lo que cogemos el arco
            answer += w;
            p[pu] = pv; // actualizamos representantes
        }
    }

    return answer;
}