Consiste en un algoritmo de
la teoría de los grafos para encontrar un árbol de cobertura mínimo en un grafo conexo (grafo que para cada par de nodos está conectado por un camino, o sea, si para cualquier par de nodos A y B, existe al menos un camino posible desde B hacia A), no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el
mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo (grafo donde hay nodos que no pueden ser conectados por medio de un camino).
Pseudocódigo
PRIM (Grafo G, nodo_fuente s)
// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL
para cada u perteneciente a V[G] hacer
distancia[u] = INFINITO;
padre[u] = NULL;
distancia[s]= 0;
//colocamos todos los nodos del grafo V, en una cola
PonerenCola(cola, V[G]);
// Se extrae el nodo que tiene distancia mínima y se conserva la condición de cola de prioridad
mientras cola != 0 hacer
u = extraer_minimo(cola);
para v perteneciente adyacencia[u] hacer
si ((v pertenece a cola) && (distancia[v]> peso(u, v)) hacer
padre[v] = u;
distancia[v] = peso(u, v);
actualizar(cola,v);
Siguiendo el algoritmo de Prim, se tiene:
- Se elige por ejemplo, el nodo 1 y se marca.
- Se elige la arista con menor valor incidente en 1, la (1, 3) = 1 se marca y se
marca el otro nodo en el que incide, el 3.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (1, 2) = 3 se marca y se marca el nodo no marcado, el 2.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (2, 5) = 5 se marca y se marca el nodo no marcado, el 5.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (5, 6) = 1 se marca y se marca el nodo no marcado, el 6.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (5, 7) = 2 se marca y se marca el nodo no marcado, el 7.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (5, 4) = 6 se marca y se marca el nodo no marcado, el 4.
- FIN. Se finaliza dado que se tiene marcados los 7 nodos del grafo.
- Por tanto el árbol de mínima expansión resultante sería:
Código en Java
public class Algorithms
{
public static Graph PrimsAlgorithm (Graph g, int s)
{
int n = g.getNumberOfVertices ();
Entry[] table = new Entry [n];
for (int v = 0; v < n; ++v)
table [v] = new Entry ();
table [s].distance = 0;
PriorityQueue queue =
new BinaryHeap (g.getNumberOfEdges());
queue.enqueue (
new Association (new Int (0), g.getVertex (s)));
while (!queue.isEmpty ())
{
Association assoc = (Association) queue.dequeueMin();
Vertex v0 = (Vertex) assoc.getValue ();
int n0 = v0.getNumber ();
if (!table [n0].known)
{
table [n0].known = true;
Enumeration p = v0.getEmanatingEdges ();
while (p.hasMoreElements ())
{
Edge edge = (Edge) p.nextElement ();
Vertex v1 = edge.getMate (v0);
int n1 = v1.getNumber ();
Int wt = (Int) edge.getWeight ();
int d = wt.intValue ();
if (!table[n1].known && table[n1].distance>d)
{ table [n1].distance = d;
table [n1].predecessor = n0;
queue.enqueue (
new Association (new Int (d), v1));
}
}
}
}
Graph result = new GraphAsLists (n);
for (int v = 0; v < n; ++v)
result.addVertex (v);
for (int v = 0; v < n; ++v)
if (v != s)
result.addEdge (v, table [v].predecessor);
return result;
}
}
Mas del algoritmo
0 comentarios: