Algoritmo Prims

Árbol de expansión mínimo:

Un gráfico que no tiene direcciones se llama gráfico no dirigido. Cada gráfico debe tener una ruta de un nodo a otro nodo. Un árbol de expansión también es un gráfico conectado no dirigido donde todos los nodos del gráfico están presentes con bordes mínimos. Si un árbol de expansión no tiene todos los nodos del gráfico, entonces no podemos decir que es un árbol de expansión. Los pesos totales del árbol de expansión serán menores que el peso original del gráfico a medida que lo conectamos a través de los bordes de peso mínimo. El árbol de expansión tampoco tiene un ciclo. Cualquier gráfico tiene más de un árbol de expansión, pero solo uno de ellos será único. Lo llamamos un árbol de expansión mínimo ya que estamos intentando crear un gráfico completo con todos los nodos mientras mantenemos el peso bajo.

Podemos dibujar un árbol de expansión con la ayuda de los siguientes dos métodos:

1. Algoritmo de Kruskal
2. Algoritmo de Prim

En este artículo, vamos a discutir el algoritmo de Prim. El algoritmo de Kruskal se discutirá en el próximo artículo.

Algoritmo de Prim:

El algoritmo de Prim se utiliza para encontrar el árbol de expansión mínimo de un gráfico. El algoritmo del Prim comienza desde cualquier nodo y luego agrega cualquier nodo adyacente cuyo peso sea el mínimo, y este proceso continúa hasta que se visitan todos los nodos en los gráficos. Al crear el árbol de expansión mínimo de un gráfico, tampoco debemos crear ningún ciclo porque los ciclos no deben estar en el árbol de expansión mínimo.

Pasos de algoritmo de Prim:

El algoritmo de Prim emplea el enfoque codicioso para el árbol mínimo de expansión. Tenemos que elegir cualquier vértice del gráfico y luego elegir el siguiente vértice de adyacencia cuyo peso es menor, y continuamos este proceso hasta que no conectamos los nodos de gráfico completos.

Paso 1: Elija cualquier vértice de origen en el gráfico.

Paso 2: Encuentre el borde de peso mínimo adyacente a la fuente y luego conéctelo al árbol de expansión.

Paso 3: Repita el paso 2 hasta que no se agregue todos los nodos al árbol de expansión mínimo.

Ejemplo :

El siguiente es un ejemplo para buscar un árbol de expansión mínimo utilizando el algoritmo de Prim.

1. Elegimos cualquier nodo aleatorio del gráfico G y lo agregamos al MST (árbol de expansión mínimo). Seleccionamos aquí nodo 0.

2. Ahora, seleccionamos ese borde adyacente al nodo fuente (0) pero con el peso más pequeño, y luego agregamos ese nodo de peso más pequeño al árbol de expansión mínimo.

3. Ahora, seleccionamos ese borde adyacente al nodo fuente (0 o 1) pero con el peso más pequeño, y luego agregamos ese nodo de peso más pequeño al árbol de expansión mínimo.

4. Ahora, seleccionamos ese borde adyacente al nodo fuente (0, 1 o 3) pero con el peso más pequeño, y luego agregamos ese nodo de peso más pequeño al árbol de expansión mínimo.

5. Ahora, seleccionamos ese borde adyacente al nodo fuente (0, 1, 3 o 4) pero con el peso más pequeño, y luego agregamos ese nodo de peso más pequeño al árbol de expansión mínimo.

6. Ahora, seleccionamos ese borde adyacente al nodo fuente (0, 1, 3, 4 o 6) pero con el peso más pequeño, y luego agregamos ese nodo de peso más pequeño al árbol de expansión mínimo.

7. Ahora, seleccionamos ese borde adyacente al nodo fuente (0, 1, 3, 4, 6 o 2) pero con el peso más pequeño, y luego agregamos ese nodo de peso más pequeño al árbol de expansión mínimo.

Arriba está nuestro MST final (árbol de expansión mínimo), y el costo total es 6.

Programa MST de C ++ Prim's (árbol de expansión mínimo):

#incluir
#incluir
#incluir
#incluir
#incluir
typedef std :: par Sii;
typedef std :: vector Ssii;
int Primsmst (int SourCenode, std :: vector & grafico)
// Esta cola almacenará los detalles de cada nodo
// junto con su valor de peso.
std :: priority_queue, std :: mayor> k;
k.push (std :: make_pair (0, SourCenode));
bool nodesadded [gráfico.tamaño()];
Memset (nodoSadded, falso, sizeof (bool)*gráfico.tamaño());
int mst_tree_cost = 0;
mientras (!k.vacío())
// Estamos seleccionando aquí el nodo que tiene un costo mínimo
Sii itemnode;
itemNode = k.arriba();
k.estallido();
int node = itemNode.segundo;
int costo = itemnode.primero;
// Aquí estamos revisando si no se ha agregado ningún nodo al MST,
// luego agregando ese nodo.
si (!nodoSadded [nodo])
mst_tree_cost += costo;
nodoSadded [nodo] = true;
// iterar sobre los nodos negibur que fueron tomados recientemente
// Fuera de la cola prioritaria.
// y agregado al MST que aún no está agregado
for (auto & par_node_cost: gráfico [nodo])
intsdency_node = par_node_cost.segundo;
if (nodesadded [adjency_node] == false)
k.push (par_node_cost);




return mst_tree_cost;

int main ()
// Los detalles del gráfico con el nodo de costo y adjencia.
Ssii fromNode_0_in_graph_1 = 1,1, 2,2, 1,3,
1,4, 2,5, 1,6;
Ssii fromNode_1_in_graph_1 = 1,0, 2,2, 2,6;
Ssii fromNode_2_in_graph_1 = 2,0, 2,1, 1,3;
Ssii fromNode_3_in_graph_1 = 1,0, 1,2, 2,4;
Ssii fromNode_4_in_graph_1 = 1,0, 2,3, 2,5;
Ssii fromNode_5_in_graph_1 = 2,0, 2,4, 1,6;
Ssii fromNode_6_in_graph_1 = 1,0, 2,2, 1,5;
int num_of_nodes = 7; // nodos totales (0 a 6)
std :: vector Primsgraph;
primsgraph.cambiar el tamaño (num_of_nodes);
primsgraph [0] = fromNode_0_in_graph_1;
primsgraph [1] = fromNode_1_in_graph_1;
primsgraph [2] = fromNode_2_in_graph_1;
primsgraph [3] = fromNode_3_in_graph_1;
primsgraph [4] = fromNode_4_in_graph_1;
primsgraph [5] = fromNode_5_in_graph_1;
primsgraph [6] = fromNode_6_in_graph_1;
// Como ya sabemos, tenemos que elegir el vértice de origen,
// Entonces comenzamos desde el nodo Vertex 0.
std :: cout << "Total cost of minimum spanning tree after Prim's algorithm : "
" << PrimsMST(0, primsgraph) << std :: endl;
regresar 0;

Producción:

Costo total del árbol de expansión mínimo después del algoritmo de Prim: 6

Complejidad del tiempo del algoritmo MST de Prim:

1. El tiempo total requerido para procesar y seleccionar el nodo de cola de prioridad específico que aún no se ha agregado al MST es logv.Pero como funciona para cada vértice, la complejidad del tiempo total es V (logv).

2. El gráfico no está dirigido y los bordes totales serán 2E. Como tenemos que empujar los nodos a la cola de prioridad, tomará un registro de tiempo total (v). Sin embargo, debido a que tenemos un total de 2e bordes, nuestra operación total de empuje será 2E (log (v)).

3. Complejidad total después de la operación 1 y 2 es O ((e + v) log (v)).

Conclusión:

Hemos estudiado el árbol de expansión mínimo del Prim, que es la primera preferencia de la mayoría de las personas cuando tienen que encontrar el gráfico MST de un gráfico. El algoritmo del Prim es fácil de comprender e implementar en una aplicación del mundo real.El algoritmo de Prim es muy útil en aplicaciones de la vida real, por ejemplo, conectando vías ferroviarias a todo sobre las ciudades. Por lo tanto, es solo un ejemplo, pero su aplicación es enorme, por lo que debemos tener que entender este algoritmo.