Árbol de expansión mínima - algoritmo de Prim

Se da un grafo ponderado no dirigido $G$ con $n$ vértices y $m$ aristas. Queremos encontrar un árbol de expansión de este grafo que conecte todos los vértices y tenga el menor peso (es decir, que la suma de los pesos de las aristas sea mínima). Un árbol de expansión es un conjunto de aristas tal que cualquier vértice puede alcanzar a cualquier otro por exactamente un camino simple. El árbol de expansión con menor peso se llama árbol de expansión mínima (MST).

En la imagen de la izquierda se ve un grafo no dirigido ponderado, y en la de la derecha el árbol de expansión mínima (MST) correspondiente.

Es fácil ver que cualquier árbol de expansión contendrá necesariamente $n-1$ aristas.

Este problema aparece de forma bastante natural en muchos problemas. Por ejemplo en el siguiente problema: hay $n$ ciudades y para cada par de ciudades se nos da el costo de construir una carretera entre ellas (o sabemos que es físicamente imposible construir una carretera entre ellas). Hay que construir carreteras de modo que se pueda ir de cada ciudad a cualquier otra, y que el costo de construir todas las carreteras sea mínimo.

Algoritmo de Prim

Este algoritmo fue descubierto originalmente por el matemático checo Vojtěch Jarník en 1930. Sin embargo, este algoritmo se conoce sobre todo como algoritmo de Prim, por el matemático estadounidense Robert Clay Prim, que lo redescubrió y republicó en 1957. Además, Edsger Dijkstra publicó este algoritmo en 1959.

Descripción del algoritmo

Aquí describimos el algoritmo en su forma más simple. El árbol de expansión mínima se construye gradualmente, agregando aristas de una en una. Al principio el árbol de expansión consiste solo en un único vértice (elegido de forma arbitraria). Luego se selecciona la arista de peso mínimo que sale de este vértice y se agrega al árbol de expansión. Después de eso el árbol de expansión ya consiste en dos vértices. Ahora se selecciona y se agrega la arista de peso mínimo que tiene un extremo en un vértice ya seleccionado (es decir, un vértice que ya forma parte del árbol de expansión) y el otro extremo en un vértice no seleccionado. Y así sucesivamente, es decir, cada vez seleccionamos y agregamos la arista de peso mínimo que conecta un vértice seleccionado con un vértice no seleccionado. El proceso se repite hasta que el árbol de expansión contiene todos los vértices (o, de forma equivalente, hasta que tengamos $n - 1$ aristas).

Al final, el árbol de expansión construido será mínimo. Si el grafo original no era conexo, entonces no existe un árbol de expansión, así que el número de aristas seleccionadas será menor que $n - 1$.

Demostración

Sea el grafo $G$ conexo, es decir, la respuesta existe. Denotamos por $T$ el grafo resultante encontrado por el algoritmo de Prim, y por $S$ el árbol de expansión mínima. Obviamente $T$ es de hecho un árbol de expansión y un subgrafo de $G$. Solo hay que mostrar que los pesos de $S$ y $T$ coinciden.

Consideremos la primera vez en el algoritmo en que agregamos a $T$ una arista que no forma parte de $S$. Denotemos esta arista por $e$, sus extremos por $a$ y $b$, y el conjunto de vértices ya seleccionados por $V$ ($a \in V$ y $b \notin V$, o viceversa).

En el árbol de expansión mínima $S$ los vértices $a$ y $b$ están conectados por algún camino $P$. En este camino podemos encontrar una arista $f$ tal que un extremo de $f$ está en $V$ y el otro no. Como el algoritmo eligió $e$ en lugar de $f$, esto significa que el peso de $f$ es mayor o igual que el peso de $e$.

Agregamos la arista $e$ al árbol de expansión mínima $S$ y eliminamos la arista $f$. Al agregar $e$ creamos un ciclo, y como $f$ también formaba parte del único ciclo, al eliminarla el grafo resultante vuelve a estar libre de ciclos. Y como solo eliminamos una arista de un ciclo, el grafo resultante sigue siendo conexo.

El árbol de expansión resultante no puede tener un peso total mayor, porque el peso de $e$ no era mayor que el peso de $f$, y tampoco puede tener un peso menor porque $S$ era un árbol de expansión mínima. Esto significa que al reemplazar la arista $f$ por $e$ generamos un árbol de expansión mínima distinto. Y $e$ tiene que tener el mismo peso que $f$.

Así, todas las aristas que elegimos en el algoritmo de Prim tienen los mismos pesos que las aristas de cualquier árbol de expansión mínima, lo que significa que el algoritmo de Prim realmente genera un árbol de expansión mínima.

Implementación

La complejidad del algoritmo depende de cómo busquemos la siguiente arista mínima entre las aristas apropiadas. Hay varios enfoques que llevan a distintas complejidades y distintas implementaciones.

Implementaciones triviales: $O(n m)$ y $O(n^2 + m \log n)$

Si buscamos la arista iterando sobre todas las aristas posibles, entonces se tarda $O(m)$ en encontrar la arista de peso mínimo. La complejidad total será $O(n m)$. En el peor caso esto es $O(n^3)$, realmente lento.

Este algoritmo se puede mejorar si solo miramos una arista desde cada vértice ya seleccionado. Por ejemplo, podemos ordenar las aristas de cada vértice en orden creciente de sus pesos, y almacenar un puntero a la primera arista válida (es decir, una arista que va a un vértice no seleccionado). Luego, después de encontrar y seleccionar la arista mínima, actualizamos los punteros. Esto da una complejidad de $O(n^2 + m)$, y por ordenar las aristas un $O(m \log n)$ adicional, lo que da la complejidad $O(n^2 \log n)$ en el peor caso.

Más abajo consideramos dos algoritmos ligeramente distintos, uno para grafos densos y otro para grafos dispersos, ambos con mejor complejidad.

Grafos densos: $O(n^2)$

Enfocamos este problema desde otro ángulo: para cada vértice todavía no seleccionado almacenaremos la arista mínima hacia un vértice ya seleccionado.

Entonces, durante un paso, solo hay que mirar estas aristas de peso mínimo, lo que tendrá complejidad $O(n)$.

Después de agregar una arista hay que recalcular algunos punteros a aristas mínimas. Nótese que los pesos solo pueden disminuir, es decir, la arista de peso mínimo de cada vértice todavía no seleccionado puede quedarse igual, o se actualizará con una arista hacia el vértice recién seleccionado. Por lo tanto esta fase también se puede hacer en $O(n)$.

Así obtenemos una versión del algoritmo de Prim con complejidad $O(n^2)$.

En particular, esta implementación es muy conveniente para el problema del árbol de expansión mínima euclidiano (Euclidean Minimum Spanning Tree): tenemos $n$ puntos en un plano y la distancia entre cada par de puntos es la distancia euclidiana entre ellos, y queremos encontrar un árbol de expansión mínima para este grafo completo. Esta tarea se puede resolver con el algoritmo descrito en tiempo $O(n^2)$ y memoria $O(n)$, lo cual no es posible con el algoritmo de Kruskal.

int n;
vector<vector<int>> adj; // matriz de adyacencia del grafo
const int INF = 1000000000; // el peso INF significa que no hay arista
 
struct Edge {
    int w = INF, to = -1;
};
 
void prim() {
    int total_weight = 0;
    vector<bool> selected(n, false);
    vector<Edge> min_e(n);
    min_e[0].w = 0;
 
    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j = 0; j < n; ++j) {
            if (!selected[j] && (v == -1 || min_e[j].w < min_e[v].w))
                v = j;
        }
 
        if (min_e[v].w == INF) {
            cout << "No MST!" << endl;
            exit(0);
        }
 
        selected[v] = true;
        total_weight += min_e[v].w;
        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;
 
        for (int to = 0; to < n; ++to) {
            if (adj[v][to] < min_e[to].w)
                min_e[to] = {adj[v][to], v};
        }
    }
 
    cout << total_weight << endl;
}

La matriz de adyacencia adj[][] de tamaño $n \times n$ almacena los pesos de las aristas, y usa el peso INF si no existe una arista entre dos vértices. El algoritmo usa dos arreglos: el flag selected[], que indica qué vértices ya hemos seleccionado, y el arreglo min_e[] que almacena, para cada vértice todavía no seleccionado, la arista de peso mínimo hacia un vértice seleccionado (almacena el peso y el vértice extremo). El algoritmo hace $n$ pasos; en cada iteración se selecciona el vértice con el menor peso de arista, y se actualiza el min_e[] de todos los demás vértices.

Grafos dispersos: $O(m \log n)$

En el algoritmo descrito arriba es posible interpretar las operaciones de encontrar el mínimo y modificar algunos valores como operaciones de conjunto. Estas dos operaciones clásicas las soportan muchas estructuras de datos, por ejemplo set en C++ (que se implementan mediante árboles rojo-negro).

El algoritmo principal se mantiene igual, pero ahora podemos encontrar la arista mínima en tiempo $O(\log n)$. Por otro lado, recalcular los punteros ahora tomará tiempo $O(n \log n)$, que es peor que en el algoritmo anterior.

Pero si consideramos que solo hay que actualizar $O(m)$ veces en total, y realizar $O(n)$ búsquedas de la arista mínima, entonces la complejidad total será $O(m \log n)$. Para grafos dispersos esto es mejor que el algoritmo de arriba, pero para grafos densos será más lento.

const int INF = 1000000000;
 
struct Edge {
    int w = INF, to = -1;
    bool operator<(Edge const& other) const {
        return make_pair(w, to) < make_pair(other.w, other.to);
    }
};
 
int n;
vector<vector<Edge>> adj;
 
void prim() {
    int total_weight = 0;
    vector<Edge> min_e(n);
    min_e[0].w = 0;
    set<Edge> q;
    q.insert({0, 0});
    vector<bool> selected(n, false);
    for (int i = 0; i < n; ++i) {
        if (q.empty()) {
            cout << "No MST!" << endl;
            exit(0);
        }
 
        int v = q.begin()->to;
        selected[v] = true;
        total_weight += q.begin()->w;
        q.erase(q.begin());
 
        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;
 
        for (Edge e : adj[v]) {
            if (!selected[e.to] && e.w < min_e[e.to].w) {
                q.erase({min_e[e.to].w, e.to});
                min_e[e.to] = {e.w, v};
                q.insert({e.w, e.to});
            }
        }
    }
 
    cout << total_weight << endl;
}

Aquí el grafo se representa mediante una lista de adyacencia adj[], donde adj[v] contiene todas las aristas (en forma de pares de peso y destino) del vértice v. min_e[v] almacenará el peso de la arista más pequeña desde el vértice v hacia un vértice ya seleccionado (de nuevo en forma de par peso y destino). Además, la cola q se llena con todos los vértices todavía no seleccionados en orden creciente de los pesos min_e. El algoritmo hace n pasos; en cada uno selecciona el vértice v con el menor peso min_e (extrayéndolo del comienzo de la cola), y luego recorre todas las aristas de este vértice y actualiza los valores en min_e (durante una actualización también hay que eliminar la arista vieja de la cola q y poner la arista nueva).