Introducción al algoritmo de Prim:
Hemos discutido Algoritmo de Kruskal para el árbol de expansión mínimo . Al igual que el algoritmo de Kruskal, el algoritmo de Prim también es un Algoritmo codicioso . Este algoritmo siempre comienza con un solo nodo y se mueve a través de varios nodos adyacentes para explorar todos los bordes conectados a lo largo del camino.
El algoritmo comienza con un árbol de expansión vacío. La idea es mantener dos conjuntos de vértices. El primer conjunto contiene los vértices ya incluidos en el MST y el otro conjunto contiene los vértices que aún no están incluidos. En cada paso, considera todos los bordes que conectan los dos conjuntos y selecciona el borde de peso mínimo de estos bordes. Después de seleccionar el borde, mueve el otro punto final del borde al conjunto que contiene MST.
Un grupo de aristas que conecta dos conjuntos de vértices en un gráfico se llama corte en la teoría de grafos . Entonces, en cada paso del algoritmo de Prim, busque un corte, elija el borde de peso mínimo del corte e incluya este vértice en el conjunto MST (el conjunto que contiene los vértices ya incluidos).
¿Cómo funciona el algoritmo de Prim?
El funcionamiento del algoritmo de Prim se puede describir mediante los siguientes pasos:
Paso 1: Determine un vértice arbitrario como vértice inicial del MST.
Paso 2: Siga los pasos 3 a 5 hasta que haya vértices que no estén incluidos en el MST (conocidos como vértices marginales).
Paso 3: Encuentre aristas que conecten cualquier vértice de árbol con los vértices marginales.
Etapa 4: Encuentra el mínimo entre estos bordes.
Paso 5: Añade el borde elegido al MST si no forma ningún ciclo.
Paso 6: Devuelve el MST y sal.
Nota: Para determinar un ciclo, podemos dividir los vértices en dos conjuntos [un conjunto contiene los vértices incluidos en MST y el otro contiene los vértices marginales].
Práctica recomendada Árbol de expansión mínima ¡Pruébelo!Ilustración del algoritmo de Prim:
Considere el siguiente gráfico como un ejemplo para el cual necesitamos encontrar el árbol de expansión mínimo (MST).
Ejemplo de un gráfico
Paso 1: En primer lugar, seleccionamos un vértice arbitrario que actúa como vértice inicial del árbol de expansión mínima. Aquí hemos seleccionado el vértice. 0 como vértice inicial.
Se selecciona 0 como vértice inicial.
Paso 2: Todas las aristas que conectan el MST incompleto y otros vértices son las aristas {0, 1} y {0, 7}. Entre estos dos, la arista con peso mínimo es {0, 1}. Así que incluya el borde y el vértice 1 en el MST.
1 se agrega al MST
Paso 3: Las aristas que conectan el MST incompleto con otros vértices son {0, 7}, {1, 7} y {1, 2}. Entre estas aristas el peso mínimo es 8 que es de las aristas {0, 7} y {1, 2}. Incluyamos aquí el borde {0, 7} y el vértice 7 en el MST. [También podríamos haber incluido el borde {1, 2} y el vértice 2 en el MST].
Se agrega 7 en el MST
Etapa 4: Las aristas que conectan el MST incompleto con los vértices marginales son {1, 2}, {7, 6} y {7, 8}. Agregue el borde {7, 6} y el vértice 6 en el MST ya que tiene el menor peso (es decir, 1).
Se agrega 6 en el MST
Paso 5: Las aristas de conexión ahora son {7, 8}, {1, 2}, {6, 8} y {6, 5}. Incluya el borde {6, 5} y el vértice 5 en el MST ya que el borde tiene el peso mínimo (es decir, 2) entre ellos.
Incluir el vértice 5 en el MST
Paso 6: Entre los bordes de conexión actuales, el borde {5, 2} tiene el peso mínimo. Así que incluya ese borde y el vértice 2 en el MST.
Incluir el vértice 2 en el MST
Paso 7: Las aristas de conexión entre el MST incompleto y las otras aristas son {2, 8}, {2, 3}, {5, 3} y {5, 4}. La arista con peso mínimo es la arista {2, 8} que tiene peso 2. Por lo tanto, incluya esta arista y el vértice 8 en el MST.
Agregar el vértice 8 en el MST
Paso 8: Vea aquí que los bordes {7, 8} y {2, 3} tienen el mismo peso, que es mínimo. Pero el 7 ya forma parte del MST. Entonces consideraremos la arista {2, 3} e incluiremos esa arista y el vértice 3 en el MST.
Incluir el vértice 3 en MST
Paso 9: Sólo queda por incluir el vértice 4. El borde ponderado mínimo desde el MST incompleto hasta 4 es {3, 4}.
Incluir el vértice 4 en el MST
La estructura final del MST es la siguiente y el peso de las aristas del MST es (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
La estructura del MST formada usando el método anterior.
Nota: Si hubiéramos seleccionado el borde {1, 2} en el tercer paso, entonces el MST tendría el siguiente aspecto.
Estructura del MST alternativo si hubiéramos seleccionado el borde {1, 2} en el MST
¿Cómo implementar el algoritmo de Prim?
Siga los pasos indicados para utilizar el Algoritmo de Prim mencionado anteriormente para encontrar MST de un gráfico:
- crear un conjunto mstSet que realiza un seguimiento de los vértices ya incluidos en MST.
- Asigne un valor clave a todos los vértices del gráfico de entrada. Inicialice todos los valores clave como INFINITO. Asigne el valor clave como 0 para el primer vértice para que se seleccione primero.
- Mientras mstSet no incluye todos los vértices
- Elige un vértice en eso no esta ahí en mstSet y tiene un valor clave mínimo.
- Incluir en en el mstSet .
- Actualice el valor clave de todos los vértices adyacentes de en . Para actualizar los valores clave, repita todos los vértices adyacentes.
- Para cada vértice adyacente en , si el peso del borde u-v es menor que el valor clave anterior de en , actualice el valor clave como el peso de u-v .
La idea de utilizar valores clave es elegir el borde de peso mínimo del cortar . Los valores clave se utilizan solo para los vértices que aún no están incluidos en MST; el valor clave para estos vértices indica los bordes de peso mínimo que los conectan al conjunto de vértices incluidos en MST.
A continuación se muestra la implementación del enfoque:
C++
// A C++ program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> using> namespace> std;> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(>int> key[],>bool> mstSet[])> {> >// Initialize min value> >int> min = INT_MAX, min_index;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] void printMST(int parent[], int graph[V][V]) { cout << 'Edge Weight
'; for (int i = 1; i cout << parent[i] << ' - ' << i << ' ' << graph[i][parent[i]] << '
'; } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // Print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; } // This code is contributed by rathbhupendra> |
>
>
C
// A C program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> #include> #include> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(>int> key[],>bool> mstSet[])> {> >// Initialize min value> >int> min = INT_MAX, min_index;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] int printMST(int parent[], int graph[V][V]) { printf('Edge Weight
'); for (int i = 1; i printf('%d - %d %d
', parent[i], i, graph[i][parent[i]]); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; }> |
>
>
Java
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency matrix> // representation of the graph> import> java.io.*;> import> java.lang.*;> import> java.util.*;> class> MST {> >// Number of vertices in the graph> >private> static> final> int> V =>5>;> >// A utility function to find the vertex with minimum> >// key value, from the set of vertices not yet included> >// in MST> >int> minKey(>int> key[], Boolean mstSet[])> >{> >// Initialize min value> >int> min = Integer.MAX_VALUE, min_index = ->1>;> >for> (>int> v =>0>; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST // stored in parent[] void printMST(int parent[], int graph[][]) { System.out.println('Edge Weight'); for (int i = 1; i System.out.println(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]]); } // Function to construct and print MST for a graph // represented using adjacency matrix representation void primMST(int graph[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in // cut int key[] = new int[V]; // To represent set of vertices included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count 1; count++) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for // vertices not yet included in MST Update // the key only if graph[u][v] is smaller // than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution t.primMST(graph); } } // This code is contributed by Aakash Hasija> |
>
>
Python3
# A Python3 program for> # Prim's Minimum Spanning Tree (MST) algorithm.> # The program is for adjacency matrix> # representation of the graph> # Library for INT_MAX> import> sys> class> Graph():> >def> __init__(>self>, vertices):> >self>.V>=> vertices> >self>.graph>=> [[>0> for> column>in> range>(vertices)]> >for> row>in> range>(vertices)]> ># A utility function to print> ># the constructed MST stored in parent[]> >def> printMST(>self>, parent):> >print>(>'Edge Weight'>)> >for> i>in> range>(>1>,>self>.V):> >print>(parent[i],>'-'>, i,>' '>,>self>.graph[i][parent[i]])> ># A utility function to find the vertex with> ># minimum distance value, from the set of vertices> ># not yet included in shortest path tree> >def> minKey(>self>, key, mstSet):> ># Initialize min value> >min> => sys.maxsize> >for> v>in> range>(>self>.V):> >if> key[v] <>min> and> mstSet[v]>=>=> False>:> >min> => key[v]> >min_index>=> v> >return> min_index> ># Function to construct and print MST for a graph> ># represented using adjacency matrix representation> >def> primMST(>self>):> ># Key values used to pick minimum weight edge in cut> >key>=> [sys.maxsize]>*> self>.V> >parent>=> [>None>]>*> self>.V># Array to store constructed MST> ># Make key 0 so that this vertex is picked as first vertex> >key[>0>]>=> 0> >mstSet>=> [>False>]>*> self>.V> >parent[>0>]>=> ->1> # First node is always the root of> >for> cout>in> range>(>self>.V):> ># Pick the minimum distance vertex from> ># the set of vertices not yet processed.> ># u is always equal to src in first iteration> >u>=> self>.minKey(key, mstSet)> ># Put the minimum distance vertex in> ># the shortest path tree> >mstSet[u]>=> True> ># Update dist value of the adjacent vertices> ># of the picked vertex only if the current> ># distance is greater than new distance and> ># the vertex in not in the shortest path tree> >for> v>in> range>(>self>.V):> ># graph[u][v] is non zero only for adjacent vertices of m> ># mstSet[v] is false for vertices not yet included in MST> ># Update the key only if graph[u][v] is smaller than key[v]> >if> self>.graph[u][v]>>0> and> mstSet[v]>=>=> False> > >and> key[v]>>self>.graph[u][v]:> >key[v]>=> self>.graph[u][v]> >parent[v]>=> u> >self>.printMST(parent)> # Driver's code> if> __name__>=>=> '__main__'>:> >g>=> Graph(>5>)> >g.graph>=> [[>0>,>2>,>0>,>6>,>0>],> >[>2>,>0>,>3>,>8>,>5>],> >[>0>,>3>,>0>,>0>,>7>],> >[>6>,>8>,>0>,>0>,>9>],> >[>0>,>5>,>7>,>9>,>0>]]> >g.primMST()> # Contributed by Divyanshu Mehta> |
>
>
C#
micricketlive
// A C# program for Prim's Minimum> // Spanning Tree (MST) algorithm.> // The program is for adjacency> // matrix representation of the graph> using> System;> class> MST {> >// Number of vertices in the graph> >static> int> V = 5;> >// A utility function to find> >// the vertex with minimum key> >// value, from the set of vertices> >// not yet included in MST> >static> int> minKey(>int>[] key,>bool>[] mstSet)> >{> >// Initialize min value> >int> min =>int>.MaxValue, min_index = -1;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print // the constructed MST stored in parent[] static void printMST(int[] parent, int[, ] graph) { Console.WriteLine('Edge Weight'); for (int i = 1; i Console.WriteLine(parent[i] + ' - ' + i + ' ' + graph[i, parent[i]]); } // Function to construct and // print MST for a graph represented // using adjacency matrix representation static void primMST(int[, ] graph) { // Array to store constructed MST int[] parent = new int[V]; // Key values used to pick // minimum weight edge in cut int[] key = new int[V]; // To represent set of vertices // included in MST bool[] mstSet = new bool[V]; // Initialize all keys // as INFINITE for (int i = 0; i key[i] = int.MaxValue; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex // First node is always root of MST key[0] = 0; parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex // from the set of vertices // not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex // to the MST Set mstSet[u] = true; // Update key value and parent // index of the adjacent vertices // of the picked vertex. Consider // only those vertices which are // not yet included in MST for (int v = 0; v // graph[u][v] is non zero only // for adjacent vertices of m // mstSet[v] is false for vertices // not yet included in MST Update // the key only if graph[u][v] is // smaller than key[v] if (graph[u, v] != 0 && mstSet[v] == false && graph[u, v] parent[v] = u; key[v] = graph[u, v]; } } // Print the constructed MST printMST(parent, graph); } // Driver's Code public static void Main() { int[, ] graph = new int[, ] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); } } // This code is contributed by anuj_67.> |
>
>
JavaScript
> // Number of vertices in the graph> let V = 5;> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> function> minKey(key, mstSet)> {> >// Initialize min value> >let min = Number.MAX_VALUE, min_index;> >for> (let v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] function printMST(parent, graph) { document.write('Edge Weight' + ' '); for (let i = 1; i document.write(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]] + ' '); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation function primMST(graph) { // Array to store constructed MST let parent = []; // Key values used to pick minimum weight edge in cut let key = []; // To represent set of vertices included in MST let mstSet = []; // Initialize all keys as INFINITE for (let i = 0; i key[i] = Number.MAX_VALUE, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first vertex. key[0] = 0; parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (let count = 0; count { // Pick the minimum key vertex from the // set of vertices not yet included in MST let u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (let v = 0; v // graph[u][v] is non zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver code let graph = [ [ 0, 2, 0, 6, 0 ], [ 2, 0, 3, 8, 5 ], [ 0, 3, 0, 0, 7 ], [ 6, 8, 0, 0, 9 ], [ 0, 5, 7, 9, 0 ] ]; // Print the solution primMST(graph); // This code is contributed by Dharanendra L V.> |
>
>Producción
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Análisis de complejidad del algoritmo de Prim:
Complejidad del tiempo: O(V2), si la entrada El gráfico se representa mediante una lista de adyacencia. , entonces la complejidad temporal del algoritmo de Prim se puede reducir a O(E * logV) con la ayuda de un montón binario. En esta implementación, siempre consideramos que el árbol de expansión comienza desde la raíz del gráfico.
Espacio Auxiliar: O(V)
Otras implementaciones del algoritmo de Prim:
A continuación se muestran algunas otras implementaciones del algoritmo de Prim.
- Algoritmo de Prim para la representación de matrices de adyacencia – En este artículo hemos discutido el método de implementación del algoritmo de Prim si el gráfico está representado por una matriz de adyacencia.
- Algoritmo de Prim para la representación de listas de adyacencia – En este artículo se describe la implementación del algoritmo de Prim para gráficos representados por una lista de adyacencia.
- Algoritmo de Prim usando cola de prioridad: En este artículo, analizamos un enfoque eficiente en el tiempo para implementar el algoritmo de Prim.
ENFOQUE OPTIMIZADO DEL ALGORITMO DE PRIM:
Intuición
- Transformamos la matriz de adyacencia en lista de adyacencia usando Lista de arreglo
. - Luego creamos una clase Pair para almacenar el vértice y su peso.
- Ordenamos la lista según el peso más bajo.
- Creamos una cola de prioridad y empujamos el primer vértice y su peso en la cola.
- Luego simplemente recorremos sus bordes y almacenamos el menor peso en una variable llamada años.
- Por fin después de todos los vértices devolvemos la ans.
Implementación
C++
#include> using> namespace> std;> typedef> pair<>int>,>int>>pii;> // Function to find sum of weights of edges of the Minimum Spanning Tree.> int> spanningTree(>int> V,>int> E,>int> edges[][3])> {> >// Create an adjacency list representation of the graph> >vectorint>> adj[V]; // Llene la lista de adyacencia con aristas y sus pesos para (int i = 0; i int u = aristas[i][0]; int v = aristas[i][1]; int wt = aristas[i][2] ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}); // Crea una cola de prioridad para almacenar bordes con sus pesos prioridad_queue pq; matriz visitada para realizar un seguimiento del vector de vértices visitados |
>
>
Java
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency list> // representation of the graph> import> java.io.*;> import> java.util.*;> // Class to form pair> class> Pair>implements> Comparable> {> >int> v;> >int> wt;> >Pair(>int> v,>int> wt)> >{> >this>.v=v;> >this>.wt=wt;> >}> >public> int> compareTo(Pair that)> >{> >return> this>.wt-that.wt;> >}> }> class> GFG {> // Function of spanning tree> static> int> spanningTree(>int> V,>int> E,>int> edges[][])> >{> >ArrayList adj=>new> ArrayList();> >for>(>int> i=>0>;i { adj.add(new ArrayList()); } for(int i=0;i { int u=edges[i][0]; int v=edges[i][1]; int wt=edges[i][2]; adj.get(u).add(new Pair(v,wt)); adj.get(v).add(new Pair(u,wt)); } PriorityQueue pq = new PriorityQueue(); pq.add(new Pair(0,0)); int[] vis=new int[V]; int s=0; while(!pq.isEmpty()) { Pair node=pq.poll(); int v=node.v; int wt=node.wt; if(vis[v]==1) continue; s+=wt; vis[v]=1; for(Pair it:adj.get(v)) { if(vis[it.v]==0) { pq.add(new Pair(it.v,it.wt)); } } } return s; } // Driver code public static void main (String[] args) { int graph[][] = new int[][] {{0,1,5}, {1,2,3}, {0,2,1}}; // Function call System.out.println(spanningTree(3,3,graph)); } }> |
>
>
Python3
import> heapq> def> tree(V, E, edges):> ># Create an adjacency list representation of the graph> >adj>=> [[]>for> _>in> range>(V)]> ># Fill the adjacency list with edges and their weights> >for> i>in> range>(E):> >u, v, wt>=> edges[i]> >adj[u].append((v, wt))> >adj[v].append((u, wt))> ># Create a priority queue to store edges with their weights> >pq>=> []> ># Create a visited array to keep track of visited vertices> >visited>=> [>False>]>*> V> ># Variable to store the result (sum of edge weights)> >res>=> 0> ># Start with vertex 0> >heapq.heappush(pq, (>0>,>0>))> ># Perform Prim's algorithm to find the Minimum Spanning Tree> >while> pq:> >wt, u>=> heapq.heappop(pq)> >if> visited[u]:> >continue> ># Skip if the vertex is already visited> >res>+>=> wt> ># Add the edge weight to the result> >visited[u]>=> True> ># Mark the vertex as visited> ># Explore the adjacent vertices> >for> v, weight>in> adj[u]:> >if> not> visited[v]:> >heapq.heappush(pq, (weight, v))> ># Add the adjacent edge to the priority queue> >return> res> ># Return the sum of edge weights of the Minimum Spanning Tree> if> __name__>=>=> '__main__'>:> >graph>=> [[>0>,>1>,>5>],> >[>1>,>2>,>3>],> >[>0>,>2>,>1>]]> ># Function call> >print>(tree(>3>,>3>, graph))> |
>
>
C#
using> System;> using> System.Collections.Generic;> public> class> MinimumSpanningTree> {> >// Function to find sum of weights of edges of the Minimum Spanning Tree.> >public> static> int> SpanningTree(>int> V,>int> E,>int>[,] edges)> >{> >// Create an adjacency list representation of the graph> >Listint[]>> adj = nuevo Listint[]>>(); para (int i = 0; i { adj.Add(nueva lista |
>
>
JavaScript
class PriorityQueue {> >constructor() {> >this>.heap = [];> >}> >enqueue(value) {> >this>.heap.push(value);> >let i =>this>.heap.length - 1;> >while> (i>0) {> >let j = Math.floor((i - 1) / 2);> >if> (>this>.heap[i][0]>=>this>.heap[j][0]) {> >break>;> >}> >[>this>.heap[i],>this>.heap[j]] = [>this>.heap[j],>this>.heap[i]];> >i = j;> >}> >}> >dequeue() {> >if> (>this>.heap.length === 0) {> >throw> new> Error(>'Queue is empty'>);> >}> >let i =>this>.heap.length - 1;> >const result =>this>.heap[0];> >this>.heap[0] =>this>.heap[i];> >this>.heap.pop();> >i--;> >let j = 0;> >while> (>true>) {> >const left = j * 2 + 1;> >if> (left>yo) {> >break>;> >}> >const right = left + 1;> >let k = left;> >if> (right <= i &&>this>.heap[right][0] <>this>.heap[left][0]) {> >k = right;> >}> >if> (>this>.heap[j][0] <=>this>.heap[k][0]) {> >break>;> >}> >[>this>.heap[j],>this>.heap[k]] = [>this>.heap[k],>this>.heap[j]];> >j = k;> >}> >return> result;> >}> >get count() {> >return> this>.heap.length;> >}> }> function> spanningTree(V, E, edges) {> >// Create an adjacency list representation of the graph> >const adj =>new> Array(V).fill(>null>).map(() =>[]);> >// Fill the adjacency list with edges and their weights> >for> (let i = 0; i const [u, v, wt] = edges[i]; adj[u].push([v, wt]); adj[v].push([u, wt]); } // Create a priority queue to store edges with their weights const pq = new PriorityQueue(); // Create a visited array to keep track of visited vertices const visited = new Array(V).fill(false); // Variable to store the result (sum of edge weights) let res = 0; // Start with vertex 0 pq.enqueue([0, 0]); // Perform Prim's algorithm to find the Minimum Spanning Tree while (pq.count>0) { constante p = pq.dequeue(); peso constante = p[0]; // Peso del borde const u = p[1]; // Vértice conectado al borde if (visitado[u]) { continuar; // Saltar si el vértice ya está visitado } res += wt; // Agrega el peso del borde al resultado visitado[u] = true; // Marca el vértice como visitado // Explora los vértices adyacentes for (const v of adj[u]) { // v[0] representa el vértice y v[1] representa el peso del borde if (!visited[v[0] ]]) { pq.enqueue([v[1], v[0]]); // Agrega el borde adyacente a la cola de prioridad } } } return res; // Devuelve la suma de los pesos de los bordes del árbol de expansión mínimo } // Ejemplo de uso const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Llamada a función console.log(spanningTree(3, 3, gráfico));> |
>
>Producción
4>
Análisis de complejidad del algoritmo de Prim:
Complejidad del tiempo: O(E*log(E)) donde E es el número de aristas
Espacio Auxiliar: O(V^2) donde V es el número de vértices
Algoritmo de Prim para encontrar el árbol de expansión mínimo (MST):
Ventajas:
- Se garantiza que el algoritmo de Prim encontrará el MST en un gráfico ponderado y conectado.
- Tiene una complejidad temporal de O (E log V) utilizando un montón binario o montón de Fibonacci, donde E es el número de aristas y V es el número de vértices.
- Es un algoritmo relativamente simple de entender e implementar en comparación con otros algoritmos MST.
Desventajas:
- Al igual que el algoritmo de Kruskal, el algoritmo de Prim puede ser lento en gráficos densos con muchas aristas, ya que requiere iterar sobre todas las aristas al menos una vez.
- El algoritmo de Prim se basa en una cola de prioridad, que puede consumir memoria adicional y ralentizar el algoritmo en gráficos muy grandes.
- La elección del nodo inicial puede afectar la salida del MST, lo que puede no ser deseable en algunas aplicaciones.