En este artículo, discutiremos el algoritmo de prim. Junto con el algoritmo, también veremos la complejidad, el funcionamiento, el ejemplo y la implementación del algoritmo de prim.
Antes de comenzar con el tema principal, debemos analizar los términos básicos e importantes, como árbol de expansión y árbol de expansión mínimo.
árbol de expansión - Un árbol de expansión es el subgrafo de un gráfico conexo no dirigido.
Árbol de expansión mínimo - El árbol de expansión mínimo se puede definir como el árbol de expansión en el que la suma de los pesos de los bordes es mínima. El peso del árbol de expansión es la suma de los pesos dados a los bordes del árbol de expansión.
Ahora comencemos con el tema principal.
Algoritmo de Prim es un algoritmo codicioso que se utiliza para encontrar el árbol de expansión mínimo a partir de un gráfico. El algoritmo de Prim encuentra el subconjunto de aristas que incluye cada vértice del gráfico de modo que la suma de los pesos de las aristas pueda minimizarse.
El algoritmo de Prim comienza con un solo nodo y explora todos los nodos adyacentes con todos los bordes de conexión en cada paso. Se seleccionaron los bordes con los pesos mínimos que no causan ciclos en el gráfico.
¿Cómo funciona el algoritmo de prim?
El algoritmo de Prim es un algoritmo codicioso que comienza desde un vértice y continúa agregando los bordes con el peso más pequeño hasta alcanzar el objetivo. Los pasos para implementar el algoritmo de prim se detallan a continuación:
- Primero, tenemos que inicializar un MST con el vértice elegido al azar.
- Ahora, tenemos que encontrar todos los bordes que conectan el árbol en el paso anterior con los nuevos vértices. De los bordes encontrados, seleccione el borde mínimo y agréguelo al árbol.
- Repita el paso 2 hasta que se forme el árbol de expansión mínimo.
Las aplicaciones del algoritmo de prim son:
- El algoritmo de Prim se puede utilizar en el diseño de redes.
- Se puede utilizar para realizar ciclos de red.
- También se puede utilizar para tender cables eléctricos.
Ejemplo de algoritmo de prim
Ahora, veamos el funcionamiento del algoritmo de prim usando un ejemplo. Será más fácil entender el algoritmo de prim usando un ejemplo.
Supongamos que un gráfico ponderado es:
Paso 1 - Primero, tenemos que elegir un vértice del gráfico anterior. Elijamos B.
variables de tipo java
Paso 2 - Ahora, tenemos que elegir y agregar la arista más corta del vértice B. Hay dos aristas del vértice B que son B a C con peso 10 y arista B a D con peso 4. Entre las aristas, la arista BD tiene el peso mínimo . Entonces, agréguelo al MST.
Paso 3 - Ahora, de nuevo, elige el borde con el peso mínimo entre todos los demás bordes. En este caso, los bordes DE y CD son tales bordes. Agréguelos al MST y explore el adyacente de C, es decir, E y A. Entonces, seleccione el borde DE y agréguelo al MST.
Etapa 4 - Ahora, seleccione el CD perimetral y agréguelo al MST.
Paso 5 - Ahora, elija la CA de borde. Aquí, no podemos seleccionar el borde CE ya que crearía un ciclo en el gráfico. Entonces, elija la CA perimetral y agréguela al MST.
Entonces, el gráfico producido en el paso 5 es el árbol de expansión mínimo del gráfico dado. El costo del MST se detalla a continuación:
Costo de MST = 4 + 2 + 1 + 3 = 10 unidades.
Algoritmo
Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT
Complejidad del algoritmo de Prim
Ahora, veamos la complejidad temporal del algoritmo de Prim. El tiempo de ejecución del algoritmo de prim depende del uso de la estructura de datos para el gráfico y del orden de los bordes. La siguiente tabla muestra algunas opciones:
| Estructura de datos utilizada para el peso mínimo del borde. | Complejidad del tiempo |
|---|---|
| Matriz de adyacencia, búsqueda lineal | O(|V|2) |
| Lista de adyacencia y montón binario | O(|E| iniciar sesión |V|) |
| Lista de adyacencia y montón de Fibonacci | O(|E|+ |V| iniciar sesión |V|) |
El algoritmo de Prim se puede implementar simplemente utilizando la matriz de adyacencia o la representación gráfica de lista de adyacencia, y para agregar el borde con el peso mínimo se requiere la búsqueda lineal de una matriz de pesos. Requiere O(|V|2) tiempo de ejecución. Se puede mejorar aún más utilizando la implementación de montón para encontrar los bordes de peso mínimo en el bucle interno del algoritmo.
La complejidad temporal del algoritmo prim es O (E logV) u O (V logV), donde E es el no. de aristas, y V es el no. de vértices.
Implementación del algoritmo de Prim.
Ahora veamos la implementación del algoritmo de prim.
Programa: Escriba un programa para implementar el algoritmo de prim en lenguaje C.
#include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
weight
'); printf(' %d
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that's all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>