En este tutorial, aprenderá cómo funciona el algoritmo de Prim. Además, encontrará ejemplos prácticos del algoritmo de Prim en C, C ++, Java y Python.
El algoritmo de Prim es un algoritmo de árbol de expansión mínimo que toma un gráfico como entrada y encuentra el subconjunto de los bordes de ese gráfico que
- formar un árbol que incluya todos los vértices
- tiene la suma mínima de pesos entre todos los árboles que se pueden formar a partir del gráfico
Cómo funciona el algoritmo de Prim
Se incluye en una clase de algoritmos llamados algoritmos codiciosos que encuentran el óptimo local con la esperanza de encontrar un óptimo global.
Comenzamos desde un vértice y seguimos agregando aristas con el peso más bajo hasta alcanzar nuestro objetivo.
Los pasos para implementar el algoritmo de Prim son los siguientes:
- Inicialice el árbol de expansión mínimo con un vértice elegido al azar.
- Encuentra todas las aristas que conectan el árbol con nuevos vértices, encuentra el mínimo y agrégalo al árbol
- Siga repitiendo el paso 2 hasta que obtengamos un árbol de expansión mínimo
Ejemplo del algoritmo de Prim
Comience con un gráfico ponderado 
Elija un vértice 
Elija el borde más corto de este vértice y agréguelo 
Elija el vértice más cercano que aún no esté en la solución 
Elija el borde más cercano que aún no esté en la solución, si hay varias opciones, elija una al azar 
Repita hasta que tener un árbol de expansión
Pseudocódigo del algoritmo de Prim
El pseudocódigo del algoritmo de prim muestra cómo creamos dos conjuntos de vértices U y VU. U contiene la lista de vértices que se han visitado y VU la lista de vértices que no. Uno por uno, movemos los vértices del conjunto VU al conjunto U conectando el borde de menor peso.
T = ∅; U = ( 1 ); while (U ≠ V) let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U; T = T ∪ ((u, v)) U = U ∪ (v)
Ejemplos de Python, Java y C / C ++
Aunque se utiliza la representación de gráficos de matriz de adyacencia, este algoritmo también se puede implementar usando la Lista de adyacencia para mejorar su eficiencia.
Python Java C C ++ # Prim's Algorithm in Python INF = 9999999 # number of vertices in graph V = 5 # create a 2d array of size 5x5 # for adjacency matrix to represent graph G = ((0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)) # create a array to track selected vertex # selected will become true otherwise false selected = (0, 0, 0, 0, 0) # set number of edge to 0 no_edge = 0 # the number of egde in minimum spanning tree will be # always less than(V - 1), where V is number of vertices in # graph # choose 0th vertex and make it true selected(0) = True # print for edge and weight print("Edge : Weight") while (no_edge G(i)(j): minimum = G(i)(j) x = i y = j print(str(x) + "-" + str(y) + ":" + str(G(x)(y))) selected(y) = True no_edge += 1
// Prim's Algorithm in Java import java.util.Arrays; class PGraph ( public void Prim(int G()(), int V) ( int INF = 9999999; int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false boolean() selected = new boolean(V); // set selected false initially Arrays.fill(selected, false); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in // graph // choose 0th vertex and make it true selected(0) = true; // print for edge and weight System.out.println("Edge : Weight"); while (no_edge < V - 1) ( // For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise // choose another vertex nearest to selected vertex at step 1. int min = INF; int x = 0; // row number int y = 0; // col number for (int i = 0; i < V; i++) ( if (selected(i) == true) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) System.out.println(x + " - " + y + " : " + G(x)(y)); selected(y) = true; no_edge++; ) ) public static void main(String() args) ( PGraph g = new PGraph(); // number of vertices in grapj int V = 5; // create a 2d array of size 5x5 // for adjacency matrix to represent graph int()() G = ( ( 0, 9, 75, 0, 0 ), ( 9, 0, 95, 19, 42 ), ( 75, 95, 0, 51, 66 ), ( 0, 19, 51, 0, 31 ), ( 0, 42, 66, 31, 0 ) ); g.Prim(G, V); ) )
// Prim's Algorithm in C #include #include #define INF 9999999 // number of vertices in graph #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G(V)(V) = ( (0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)); int main() ( int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected(V); // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected(0) = true; int x; // row number int y; // col number // print for edge and weight printf("Edge : Weight"); while (no_edge < V - 1) ( //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) ( if (selected(i)) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) printf("%d - %d : %d", x, y, G(x)(y)); selected(y) = true; no_edge++; ) return 0; )
// Prim's Algorithm in C++ #include #include using namespace std; #define INF 9999999 // number of vertices in grapj #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G(V)(V) = ( (0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)); int main() ( int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected(V); // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected(0) = true; int x; // row number int y; // col number // print for edge and weight cout << "Edge" << " : " << "Weight"; cout << endl; while (no_edge < V - 1) ( //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) ( if (selected(i)) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) cout << x << " - " << y << " : " << G(x)(y); cout << endl; selected(y) = true; no_edge++; ) return 0; )
Algoritmo de Prim vs Kruskal
El algoritmo de Kruskal es otro algoritmo de árbol de expansión mínimo popular que utiliza una lógica diferente para encontrar el MST de un gráfico. En lugar de comenzar desde un vértice, el algoritmo de Kruskal ordena todos los bordes de bajo peso a alto y sigue agregando los bordes más bajos, ignorando aquellos bordes que crean un ciclo.
Complejidad del algoritmo de Prim
La complejidad temporal del algoritmo de Prim es O(E log V).
Aplicación del algoritmo de Prim
- Tendido de cables de cableado eléctrico.
- En red diseñada
- Hacer protocolos en ciclos de red
