Gráficos en Java: Árboles de expansión mínimos - Algoritmo de Prim

En esta guía detallada, veremos el Algoritmo de Prim y cómo encontrar un MST (Árbol de expansión mínimo) en un gráfico en Java en teoría y práctica.

Introducción

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática.

Debido al hecho de que muchas cosas se pueden representar como gráficos, el recorrido de gráficos se ha convertido en una tarea común, especialmente utilizada en ciencia de datos y aprendizaje automático.

¿Cómo funciona el algoritmo de Prim?

El Algoritmo de Prim fue diseñado para encontrar un Árbol de expansión mínimo (MST) para un Gráfico no dirigido, ponderado y conectado. Esto significa que el algoritmo encuentra un "árbol" (una estructura que no tiene ciclos) que conecta todos los vértices a través de un subconjunto de todos los bordes disponibles que tienen el menor peso.

{.icon aria-hidden=“true”}

Al igual que el algoritmo de Dijkstra, el de Prim es un algoritmo codicioso, pero el de Prim permite bordes con ponderación negativa.

Al final del algoritmo, recorreremos nuestra matriz que contiene los bordes de menor costo y los sumaremos, obteniendo el valor del MST dentro de nuestro gráfico.

Discutiremos cómo funciona cada paso de este algoritmo, pero se puede presentar un bosquejo aproximado del algoritmo. Suponiendo que tenemos un gráfico ponderado G con un conjunto de vértices (nodos) V y un conjunto de aristas E:

  • Elegimos uno de los nodos s como el nodo inicial, y establecemos la distancia de s a s como 0.
  • Asignaremos un número desde el nodo s a cada otro nodo, marcándolo como infinito al principio. Este número cambiará y se actualizará a medida que avancemos en el algoritmo.
  • Cada nodo s también tendrá un número que representa el nodo "padre", desde el cual lo conectamos en el MST. Este número se inicializa como -1, y todos los demás nodos excepto el nodo inicial tendrá un número diferente de -1 asociado al final del algoritmo de Prim.
  • Para cada nodo s encontraremos el borde mínimo que conecta un nodo que no ya está incluido en el MST. Dado que Prim es un algoritmo codicioso, una vez que ingresamos al nodo, estamos seguros de que hemos elegido la ruta más corta que lo conecta con su padre. Repetimos este paso hasta que todos los nodos se agreguen al MST.
  • Finalmente, recorremos nuestra matriz MST y sumamos los bordes, obteniendo el valor del MST.

Visualización del algoritmo de Prim

Visualicemos rápidamente un ejemplo simple, y usemos manualmente el algoritmo de Prim para encontrar un árbol de expansión mínimo en el siguiente gráfico:

graphClanak

Tendremos 5 nodos, numerados del 0 al 4, y en cada uno de los bordes el número representa el peso de ese borde. Describamos el par INF/-1: -1 al principio representa el padre desde el cual hay un borde que se conecta al nodo actual que tiene el peso INF. Por supuesto, a medida que avanza el algoritmo, estos valores también se actualizarán.

Digamos que 0 será nuestro nodo inicial. Mencionamos anteriormente que cuando elegimos nuestro nodo inicial, debemos establecer la distancia de sí mismo como 0. Dado que 0 es el nodo con el borde mínimo a sí mismo, podemos asumir con seguridad que 0 pertenece al MST y lo agregaremos. Después de ese pequeño cambio, el gráfico queda de la siguiente manera:

graphClanak1step

{.icon aria-hidden=“true”}

Los nodos blancos representan los que agregamos al MST.

El siguiente paso es el que hace que el algoritmo de Prim sea lo que es. Recorremos todos los vecinos del nodo 0, verificando algunas cosas en el camino:

  1. Si el borde existe en absoluto
  2. Si el nodo vecino ya está agregado al MST
  3. Si el costo del borde que conduce al vecino es menor que el borde actual de menor costo que conduce a ese vecino

El primer vecino de 0 es 1. El borde que los conecta tiene un peso de 1. El borde existe, y el nodo actual 1 no está en el MST, por lo que lo único que queda es verificar si el borde de 0 a 1 es el borde ponderado más pequeño que lleva al nodo 1. Obviamente, 1 es menor que INF, por lo que actualizamos el par distancia/padre del nodo 1 a 1/0.

Seguimos exactamente los mismos pasos para todos los demás vecinos del nodo 0, después de lo cual elegimos el nodo con el peso de borde mínimo para agregarlo al MST y lo marcamos en azul. Ese nodo aquí es 1.

Ahora tenemos el siguiente gráfico:

graphClanak2step

El nodo que estamos considerando ahora es 1. Como hemos hecho con el nodo 0, verificamos todos los vecinos del nodo 1.

El nodo 0 ya se agregó al MST, por lo que omitiremos ese.

El nodo 2 es el siguiente vecino, y el peso del borde que conduce a él desde el nodo 1 es 2. Esta arista tiene un peso menor que la que conducía previamente a ese nodo, que tenía un peso de ‘5’ y provenía del nodo ‘0’.

Lo mismo ocurre con el otro nodo vecino 4: el peso de la arista que conduce a él desde el nodo 1 es 1, y anteriormente la arista ponderada más pequeña que conduce al nodo 4 desde el nodo 0 era 4 .

Elegimos el siguiente nodo que no está agregado al MST y tiene el borde ponderado más pequeño del nodo 1. Ese nodo aquí es el nodo 4.

Después de la actualización tenemos el siguiente gráfico:

graphClanak3step

Cuando consideramos el nodo 4, vemos que no podemos actualizar ninguno de los bordes actuales. Es decir, ambos vecinos del nodo 4 ya pertenecen al MST, por lo que no hay nada que actualizar allí, y simplemente avanzamos en el algoritmo sin hacer nada en este paso.

Seguimos buscando un nodo que esté conectado a un nodo perteneciente al MST y tenga la arista ponderada más pequeña posible. Ese nodo es actualmente 2 y se conecta al nodo 1 a través del borde que tiene el peso de 2. El gráfico queda de la siguiente manera:

graphClanak4step

Ambos nodos 0 y 1 ya pertenecen al MST, por lo que el único nodo posible al que podemos ir es 3. El peso del borde que conduce al nodo ‘3’ desde el nodo ‘2’ es ‘4’, que obviamente es menor que los ‘10’ anteriores que conducen al nodo ‘0’. Actualizamos eso, obteniendo el siguiente gráfico:

graphClanak5step

Con esto, hemos visitado y agregado todos los nodos existentes al MST, y debido a que Prim es un algoritmo codicioso, esto significa que hemos encontrado nuestro MST.

Recordemos; los bordes que se agregaron a la matriz que realiza un seguimiento de nuestro MST son los siguientes:

  • Flanco 0-1 de peso 1
  • Borde 1-2 de peso 2
  • Borde 1-4 de peso 1
  • Filo 2-3 de peso 4

Todo lo que queda es sumar todos los bordes que componen el MST, después de lo cual obtenemos que el valor del MST para el gráfico en nuestro ejemplo es 8, y terminamos la ejecución del algoritmo aquí. .

La complejidad temporal del algoritmo de Prim es O((|E| + |V|)log|V|), donde |E| es el número de aristas en el gráfico, y |V| es el número de vértices (nodos) en el gráfico.

Implementación del algoritmo de Prim en Java

Con la idea general y la visualización fuera del camino, implementemos el algoritmo de Prim en Java.

Como de costumbre, usaremos la implementación de gráficos ponderados de nuestro artículo anterior: Representación de gráficos en código. Sin embargo, tendremos que modificarlo ligeramente para que se ajuste a nuestras necesidades al implementar el algoritmo de Prim.

En esta guía, utilizaremos el enfoque de matriz de adyacencia. Tenga en cuenta que también podemos implementar el algoritmo de Prim usando listas de adyacencia, pero el enfoque de matriz es un poco más fácil y el código se vuelve más corto y más legible.

Una cosa importante a tener en cuenta para más adelante es que, cuando hayamos inicializado nuestra matriz de adyacencia, todos los lugares que no tengan un peso asignado se inicializarán automáticamente como 0.

Implementación de la clase Graph

En primer lugar, comenzaremos agregando tres nuevas matrices a nuestra clase Graph:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Graph {

    private int numOfNodes;
    private boolean directed;
    private boolean weighted;
    private double[][] matrix;
    
    private double[] edges;
    private double[] parents;
    private boolean[] includedInMST;
    
    private boolean[][] isSetMatrix;
   
    // ...
}

Repasemos brevemente lo que representa cada una de estas matrices:

  • bordes representa una matriz que contiene los valores de los bordes que pertenecen al MST que conecta un nodo a su padre.
  • parents nos da información sobre el padre de cada nodo.
  • includedInMST nos dice si un nodo que estamos buscando ya pertenece al MST.

Luego, los agregaremos al constructor junto con las variables previamente declaradas:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public Graph(int numOfNodes, boolean directed, boolean weighted) {
    this.directed = directed;
    this.weighted = weighted;
    this.numOfNodes = numOfNodes;

    // Simply initializes our adjacency matrix to the appropriate size
    matrix = new double[numOfNodes][numOfNodes];
    isSetMatrix = new boolean[numOfNodes][numOfNodes];
    
    edges = new double[numOfNodes];
    parents = new double[numOfNodes];
    includedInMST = new boolean[numOfNodes];

    for(int i = 0; i < numOfNodes; i++){
        edges[i] = Double.POSITIVE_INFINITY;
        parents[i] = -1;
        includedInMST[i] = false;
    }
}

Hemos asignado espacio numOfNodes para cada una de nuestras matrices individuales. Un paso importante aquí es la inicialización:

  • La distancia a cada nodo individual al principio se establece en Double.POSITIVE_INFINITY. Básicamente, esto significa que aún no hemos llegado al nodo desde ningún otro nodo, por lo tanto, la distancia hasta él es ‘Infinito’. Este número también representa Infinity como un tipo de datos en Java.
  • Dado que no se alcanza ninguno de los nodos cuando comienza el algoritmo, el padre de cada nodo se establece en -1, lo que indica que el nodo específico no tiene ningún padre desde el que se alcance. La razón por la que podemos establecer el valor de los padres en -1 es que etiquetamos los nodos de 0 a n-1 donde n es el número de nodos, por lo que lógicamente no tiene sentido tener un nodo -1.
  • Al comienzo del algoritmo, ninguno de los nodos pertenece al MST, por lo que es lógico no incluir ninguno de ellos, es decir, establecer el valor de cada miembro en includedInMST en false.

Los métodos addEdge() y printMatrix() siguen siendo los mismos, ya que ambos se explican por sí mismos para lo que hacen, no profundizaremos en eso.

Sin embargo, requerimos getters y setters adicionales que nos permitirán cambiar las matrices antes mencionadas. Esos son los siguientes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int getNumOfNodes() {
    return numOfNodes;
}

public double getEdges(int i) {
    return edges[i];
}

public void setEdges(double edge, int node) {
    this.edges[node] = edge;
}

public boolean getIncludedInMST(int i) {
    return includedInMST[i];
}

public void setIncludedInMST(int node) {
    this.includedInMST[node] = true;
}

public double[][] getMatrix() {
    return matrix;
}

public void setParents(double parent, int node) {
    this.parents[node] = parent;
}

public double getParents(int i) { 
   return parents[i]; 
}

{.icon aria-hidden=“true”}

Si alguno de estos getters/setters no es intuitivo, cada uno de los getters y setters se explicará adicionalmente a medida que los usamos al implementar el algoritmo de Prim.

Con esto, hemos completado la adaptación de la implementación de un ‘Gráfico’ ponderado, y podemos pasar al algoritmo en sí.

Implementación del algoritmo de Prim

Con un Graph listo, podemos seguir adelante e implementar el algoritmo que se ejecutará sobre él. Vamos a inicializar un Gráfico con un conjunto de nodos y sus bordes. Usaremos el mismo conjunto de nodos y aristas que en la visualización de una sección anterior:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Prim {
    public static void main(String[] args){
        Graph graph = new Graph(5, false, true);

        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 5);
        graph.addEdge(0, 3, 10);
        graph.addEdge(0, 4, 4);
        graph.addEdge(1, 2, 2);
        graph.addEdge(1, 4, 1);
        graph.addEdge(2, 3, 4);
        
        // ...
    }
}

Imprimir esta matriz usando graph.printMatrix() genera lo siguiente:

1
2
3
4
5
 /       1.0     5.0    10.0     4.0
 1.0     /       2.0     /       1.0
 5.0     2.0     /       4.0     /
10.0     /       4.0     /       /
 4.0     1.0     /       /       /

También necesitamos un método llamado minEdgeNotIncluded() que encuentre el borde ponderado mínimo que conduce a un vecino que aún no está incluido en el MST:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public static int minEdgeNotIncluded(Graph graph){
    double min = Double.POSITIVE_INFINITY;
    int minIndex = -1;
    int numOfNodes = graph.getNumOfNodes();

    for(int i = 0; i < numOfNodes; i++){
        if(!graph.getIncludedInMST(i) && graph.getEdges(i) < min){
            minIndex = i;
            min = graph.getEdges(i);
        }
    }
    return minIndex;
}

Al principio, establecemos min en Infinity, lo que indica que aún no hemos encontrado el borde mínimo. La variable minIndex representa el nodo al que se conecta el borde mínimo que estamos buscando, y lo inicializamos en -1 al principio. Luego, recorremos todos los nodos, buscando un nodo que aún no esté incluido en el MST, después de lo cual verificamos si el borde que se conecta a ese nodo es más pequeño que nuestro borde min actual.

Finalmente, estamos listos para implementar el algoritmo de Prim:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Prim {
    public static void main(String[] args){
        // Initialized and added the graph earlier
        
        int startNode = 0;
        // Distance from the start node to itself is 0
        graph.setEdges(0, startNode); 

        for(int i = 0; i < graph.getNumOfNodes()-1; i++){
            int node = minEdgeNotIncluded(graph);

            graph.setIncludedInMST(node);

            double[][] matrix = graph.getMatrix();
            for(int v = 0; v < graph.getNumOfNodes(); v++){
                if(matrix[node][v] != 0 && 
                   !graph.getIncludedInMST(v) && 
                   matrix[node][v] < graph.getEdges(v)){
                    graph.setEdges(matrix[node][v], v);
                    graph.setParents(node, v);
                }
            }
        }
        
        double cost = 0;
        for(int i = 0; i < graph.getNumOfNodes(); i++){
            if(i != startNode){
                cost += graph.getEdges(i);
            }
        }
        System.out.println(cost);
    }
}

El código en sí puede ser un poco confuso, así que profundicemos en él y expliquemos qué hace cada sección.

En primer lugar, elegimos nuestro startNode para que sea 0. Recuerde, necesitamos un nodo desde el que empezar, y ese nodo podría ser cualquier nodo del conjunto, pero para este ejemplo será 0. Establecemos la distancia desde el nodo 0 a sí mismo para que sea 0.

En el ciclo for, para cada i desde 0 hasta n-1 buscamos un nodo s de modo que el borde i-s sea el borde más pequeño desde i. Después de que hayamos encontrado el nodo correspondiente, dado que Prim es un algoritmo codicioso, estamos seguros de que no hay un borde más pequeño desde el nodo i a cualquier otro nodo además de s, por lo que agregamos s al MST.

Lo siguiente es pasar por todos los vecinos del nodo s. Recordemos cómo se tratan los pesos no inicializados en una matriz de adyacencia:

Todos los lugares en nuestra matriz de adyacencia a los que no se les ha asignado un peso se inicializarán automáticamente como 0.

Esto es importante porque cualquier (negativo o positivo) número en la posición matriz[i][j] indica que existe un borde entre los nodos i y j, mientras que 0 indica la ausencia de eso.

Por lo tanto, las condiciones que deben cumplirse para que se agregue un borde (y un nodo) al MST son las tres siguientes:

  1. Verificamos si el valor matrix[i][j] es diferente a 0, y si lo es, sabemos que el borde existe, y ese valor representa el peso entre los nodos i y j.
  2. Verificamos si el vecino ya fue agregado al MST. Si es así, salteamos ese nodo y pasamos al siguiente vecino.
  3. Si el valor del borde del nodo i al nodo j es menor que el valor ya existente de un nodo diferente al nodo j, actualizamos el par de distancia/principal para reflejar la situación, es decir, la distancia se convierte en el valor de la arista i-j y el padre desde el que llegamos al nodo j es el nodo i.

Eso resume cómo funciona el algoritmo de Prim. Todo lo que queda por hacer es revisar la matriz bordes y sumar todos los bordes que componen el MST, encontrando su valor. Eso es exactamente lo que hace la última parte de nuestro código, y almacena el resultado en la variable cost.

Terminemos el algoritmo con la salida del MST:

1
2
3
4
System.out.println("MST consists of the following edges:");
    for(int i = 1; i < graph.getNumOfNodes(); i++){
      System.out.println("edge: (" + (int)graph.getParents(i) + ", " + i + "), weight: " + graph.getEdges(i));
}

Ejecutémoslo y veamos el resultado:

1
2
3
4
5
MST consists of the following edges:
edge: (0, 1), weight: 1.0
edge: (1, 2), weight: 2.0
edge: (2, 3), weight: 4.0
edge: (1, 4), weight: 1.0

Conclusión

En esta guía, hemos cubierto y explicado cómo usar el Algoritmo de Prim para encontrar un Árbol de expansión mínima (MST) en Java.

El de Prim, junto con el algoritmo de Kruskal, es uno de los dos más utilizados para resolver este problema, que encuentra su uso en campos como el diseño de redes informáticas, redes de telecomunicaciones y redes en general.