algorithm
Algoritmo de Prim
Buscar..
Introducción al algoritmo de Prim
Digamos que tenemos 8 casas. Queremos configurar líneas telefónicas entre estas casas. El borde entre las casas representa el costo de establecer la línea entre dos casas.
Nuestra tarea es configurar líneas de tal manera que todas las casas estén conectadas y el costo de configurar toda la conexión sea mínimo. Ahora, ¿cómo averiguamos eso? Podemos usar el algoritmo de Prim .
El algoritmo de Prim es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico no dirigido ponderado. Esto significa que encuentra un subconjunto de los bordes que forma un árbol que incluye todos los nodos, donde se minimiza el peso total de todos los bordes del árbol. El algoritmo fue desarrollado en 1930 por el matemático checo Vojtěch Jarník y luego redescubierto y publicado por el científico informático Robert Clay Prim en 1957 y Edsger Wybe Dijkstra en 1959. También se conoce como algoritmo DJP , algoritmo de Jarnik, algoritmo de Prim-Jarnik o algoritmo de Prim-Dijsktra. algoritmo
Ahora veamos los términos técnicos primero. Si creamos un gráfico, S utilizando algunos nodos y bordes de un gráfico G no dirigido, entonces S se llama un subgrafo del gráfico G. Ahora S se llamará árbol de expansión si y solo si:
- Contiene todos los nodos de G.
- Es un árbol, eso significa que no hay ciclo y todos los nodos están conectados.
- Hay (n-1) bordes en el árbol, donde n es el número de nodos en G.
Puede haber muchos árboles de expansión de un gráfico. El árbol de expansión mínima de un gráfico no dirigido ponderado es un árbol, por lo que la suma del peso de los bordes es mínima. Ahora usaremos el algoritmo de Prim para averiguar el árbol de expansión mínimo, que es cómo configurar las líneas telefónicas en nuestro gráfico de ejemplo de tal manera que el costo de configuración sea mínimo.
Al principio seleccionaremos un nodo fuente . Digamos que el nodo-1 es nuestra fuente . Ahora agregaremos el borde del nodo-1 que tiene el costo mínimo para nuestro subgrafo. Aquí marcamos los bordes que están en el subgrafo usando el color azul . Aquí 1-5 es nuestro borde deseado. 
Ahora consideramos todos los bordes del nodo 1 y el nodo 5 y tomamos el mínimo. Como 1-5 ya está marcado, tomamos 1-2 . 
Esta vez, consideramos los nodos-1 , nodos-2 y nodos-5 y tomamos el borde mínimo que es 5-4 . 
El siguiente paso es importante. Desde el nodo 1 , el nodo 2 , el nodo 5 y el nodo 4 , el límite mínimo es 2-4 . Pero si seleccionamos ese, creará un ciclo en nuestro subgrafo. Esto se debe a que node-2 y node-4 ya están en nuestro subgrafo. Así que tomar ventaja 2-4 no nos beneficia. Seleccionaremos los bordes de tal manera que agregue un nuevo nodo en nuestro subgrafo . Así que seleccionamos el borde 4-8 . 
Si continuamos de esta manera, seleccionaremos el borde 8-6 , 6-7 y 4-3 . Nuestro subgrafo se verá como: 
Este es nuestro subgrafo deseado, que nos dará el árbol de expansión mínimo. Si eliminamos los bordes que no seleccionamos, obtendremos: 
Este es nuestro árbol de expansión mínima (MST). Entonces, el costo de configurar las conexiones telefónicas es: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 . Y el conjunto de casas y sus conexiones se muestran en el gráfico. Puede haber múltiples MST de un gráfico. Depende del nodo fuente que elijamos.
El pseudocódigo del algoritmo se da a continuación:
Procedure PrimsMST(Graph): // here Graph is a non-empty connected weighted graph
Vnew[] = {x} // New subgraph Vnew with source node x
Enew[] = {}
while Vnew is not equal to V
u -> a node from Vnew
v -> a node that is not in Vnew such that edge u-v has the minimum cost
// if two nodes have same weight, pick any of them
add v to Vnew
add edge (u, v) to Enew
end while
Return Vnew and Enew
Complejidad:
La complejidad temporal del enfoque ingenuo anterior es O (V²) . Utiliza matriz de adyacencia. Podemos reducir la complejidad usando la cola de prioridad. Cuando agregamos un nuevo nodo a Vnew , podemos agregar sus bordes adyacentes en la cola de prioridad. Luego saca el borde mínimo ponderado de él. Entonces la complejidad será: O (ElogE) , donde E es el número de bordes. Nuevamente, se puede construir un montón binario para reducir la complejidad a O (ElogV) .
El pseudocódigo que utiliza la cola de prioridad se muestra a continuación:
Procedure MSTPrim(Graph, source):
for each u in V
key[u] := inf
parent[u] := NULL
end for
key[source] := 0
Q = Priority_Queue()
Q = V
while Q is not empty
u -> Q.pop
for each v adjacent to i
if v belongs to Q and Edge(u,v) < key[v] // here Edge(u, v) represents
// cost of edge(u, v)
parent[v] := u
key[v] := Edge(u, v)
end if
end for
end while
Aquí la clave [] almacena el costo mínimo de atravesar node-v . parent [] se utiliza para almacenar el nodo padre. Es útil para atravesar e imprimir el árbol.
A continuación se muestra un programa simple en Java:
import java.util.*;
public class Graph
{
private static int infinite = 9999999;
int[][] LinkCost;
int NNodes;
Graph(int[][] mat)
{
int i, j;
NNodes = mat.length;
LinkCost = new int[NNodes][NNodes];
for ( i=0; i < NNodes; i++)
{
for ( j=0; j < NNodes; j++)
{
LinkCost[i][j] = mat[i][j];
if ( LinkCost[i][j] == 0 )
LinkCost[i][j] = infinite;
}
}
for ( i=0; i < NNodes; i++)
{
for ( j=0; j < NNodes; j++)
if ( LinkCost[i][j] < infinite )
System.out.print( " " + LinkCost[i][j] + " " );
else
System.out.print(" * " );
System.out.println();
}
}
public int unReached(boolean[] r)
{
boolean done = true;
for ( int i = 0; i < r.length; i++ )
if ( r[i] == false )
return i;
return -1;
}
public void Prim( )
{
int i, j, k, x, y;
boolean[] Reached = new boolean[NNodes];
int[] predNode = new int[NNodes];
Reached[0] = true;
for ( k = 1; k < NNodes; k++ )
{
Reached[k] = false;
}
predNode[0] = 0;
printReachSet( Reached );
for (k = 1; k < NNodes; k++)
{
x = y = 0;
for ( i = 0; i < NNodes; i++ )
for ( j = 0; j < NNodes; j++ )
{
if ( Reached[i] && !Reached[j] &&
LinkCost[i][j] < LinkCost[x][y] )
{
x = i;
y = j;
}
}
System.out.println("Min cost edge: (" +
+ x + "," +
+ y + ")" +
"cost = " + LinkCost[x][y]);
predNode[y] = x;
Reached[y] = true;
printReachSet( Reached );
System.out.println();
}
int[] a= predNode;
for ( i = 0; i < NNodes; i++ )
System.out.println( a[i] + " --> " + i );
}
void printReachSet(boolean[] Reached )
{
System.out.print("ReachSet = ");
for (int i = 0; i < Reached.length; i++ )
if ( Reached[i] )
System.out.print( i + " ");
//System.out.println();
}
public static void main(String[] args)
{
int[][] conn = {{0,3,0,2,0,0,0,0,4}, // 0
{3,0,0,0,0,0,0,4,0}, // 1
{0,0,0,6,0,1,0,2,0}, // 2
{2,0,6,0,1,0,0,0,0}, // 3
{0,0,0,1,0,0,0,0,8}, // 4
{0,0,1,0,0,0,8,0,0}, // 5
{0,0,0,0,0,8,0,0,0}, // 6
{0,4,2,0,0,0,0,0,0}, // 7
{4,0,0,0,8,0,0,0,0} // 8
};
Graph G = new Graph(conn);
G.Prim();
}
}
Compila el código anterior usando javac Graph.java
Salida:
$ java Graph
* 3 * 2 * * * * 4
3 * * * * * * 4 *
* * * 6 * 1 * 2 *
2 * 6 * 1 * * * *
* * * 1 * * * * 8
* * 1 * * * 8 * *
* * * * * 8 * * *
* 4 2 * * * * * *
4 * * * 8 * * * *
ReachSet = 0 Min cost edge: (0,3)cost = 2
ReachSet = 0 3
Min cost edge: (3,4)cost = 1
ReachSet = 0 3 4
Min cost edge: (0,1)cost = 3
ReachSet = 0 1 3 4
Min cost edge: (0,8)cost = 4
ReachSet = 0 1 3 4 8
Min cost edge: (1,7)cost = 4
ReachSet = 0 1 3 4 7 8
Min cost edge: (7,2)cost = 2
ReachSet = 0 1 2 3 4 7 8
Min cost edge: (2,5)cost = 1
ReachSet = 0 1 2 3 4 5 7 8
Min cost edge: (5,6)cost = 8
ReachSet = 0 1 2 3 4 5 6 7 8
0 --> 0
0 --> 1
7 --> 2
0 --> 3
3 --> 4
2 --> 5
5 --> 6
1 --> 7
0 --> 8
