Aprenda a usar el algoritmo de Prim, un método codicioso para encontrar el árbol de expansión mínimo de un gráfico ponderado, y cómo dominar las preguntas del algoritmo de Prim en las entrevistas.

Prim's algorithm is used to find the Minimum Spanning Tree (MST) of a given weighted graph. MST means that connecting all the nodes of the given graph with the minimum weights of each connection. Simply, it works like this. Take any node as a root node. From the root node, check what are the adjacent nodes of that root node. Look for the one with minimum weight. Connect that node to the root node. Now, you have 2 nodes in your MST. Later, look for the minimum weighted adjacent node from both the nodes in your MST. Connect the minimum weighted node to your MST and so on until you have all the nodes covered in your MST. Finally the tree obtained is the Minimum Spanning Tree.

¿Cómo se utiliza el algoritmo de Prim para encontrar árboles de expansión mínimos?

Con tecnología de la IA y la comunidad de LinkedIn

Encontrar el árbol de expansión mínimo (MST) de un grafo ponderado es un problema común en algoritmos y estructuras de datos. Un MST es un subconjunto de aristas que conecta todos los vértices del grafo sin formar ningún ciclo y con el mínimo peso total posible. Una forma de encontrar un MST es usar el algoritmo de Prim, que es un método codicioso que construye el MST borde por borde. En este artículo, aprenderá cómo usar el algoritmo de Prim para encontrar MST y cuáles son sus ventajas y desventajas.

Expertos destacados en este artículo

Elección de la comunidad a partir de 5 contribuciones. Más información

1 Cómo funciona el algoritmo de Prim

El algoritmo de Prim comienza con un vértice arbitrario y agrega el borde con el peso más pequeño que lo conecta a otro vértice que aún no está en el MST. Luego, repite este proceso hasta que todos los vértices estén incluidos en el MST. En cada paso, el algoritmo mantiene un conjunto de vértices que forman parte del MST y una cola de prioridad de bordes que son candidatos para agregarse al MST. La cola de prioridad se ordena por el peso del borde, por lo que el algoritmo siempre elige el borde con el peso más bajo de la cola.

Añade tu opinión

Harshendra Subba Reddy Nallamilli

Soon-to-be "PD Intern" @Darwinbox💙 & Knight👑 @LeetCode (Top 1.73% & Max. Rating 2091) & Pupil💚 @CodeForces (Max. Rating 1375) & 3⭐ @CodeChef (Max. Rating 1719) & 4⭐ @GeeksforGeeks (Max. Rating 1990)
(editado)
Denunciar la contribución
Prim's algorithm is used to find the Minimum Spanning Tree (MST) of a given weighted graph. MST means that connecting all the nodes of the given graph with the minimum weights of each connection. Simply, it works like this. Take any node as a root node. From the root node, check what are the adjacent nodes of that root node. Look for the one with minimum weight. Connect that node to the root node. Now, you have 2 nodes in your MST. Later, look for the minimum weighted adjacent node from both the nodes in your MST. Connect the minimum weighted node to your MST and so on until you have all the nodes covered in your MST. Finally the tree obtained is the Minimum Spanning Tree.

Traducido

Recomendar
Neha Pathak

5 years in Software |Software Intern | Ex Senior Software Analyst at Accenture | SQL, Power BI Certified| Automation | Machine Learning| Software Testing | NLP |Purdue University
Denunciar la contribución
In simple words to understand, this algorithm aims in getting an entire path covering all vertices of graph from one selected vertex to GET MINIMUM WEIGHT SUM ON ADDING WEIGHTS OF ALL SUB PATHS TRAVERSED. Everytime select next vertex by checking which sub path has smallest weight value ( cost of traveling that path from current vertex to destination vertex). And again recheck if total sum of weights is least.

Traducido

Recomendar

2 Cómo implementar el algoritmo de Prim

La implementación del algoritmo de Prim requiere una estructura de datos para almacenar el gráfico y sus pesos, como una matriz de adyacencia o una lista de adyacencia. Además, se necesita una estructura de datos de cola de prioridad, como un montón binario o un montón de Fibonacci. El algoritmo se puede resumir de la siguiente manera: inicialmente, inicializar un árbol de expansión mínimo vacío (MST) y cola de prioridad. A continuación, seleccione un vértice arbitrario y márquelo como visitado. Agregue todas las aristas del vértice visitado a la cola de prioridad. Si bien la cola de prioridad no está vacía y el MST tiene menos de n aristas, donde n es el número de vértices del gráfico, extraiga la arista con el peso más bajo de la cola de prioridad. Si conecta un vértice visitado y uno no visitado, agréguelo al MST y marque el vértice no visitado como visitado. Agregue todas las aristas del vértice recién visitado a la cola de prioridad. Por último, devuelva el MST. Por ejemplo, en Python con una matriz de adyacencia y un montón binario, este algoritmo se puede implementar como se muestra en el código.

Añade tu opinión

Bhavana P

Detail-Oriented Data Analyst | 5 ⭐ SQL Hackerrank| 5 ⭐ Python Hackerrank | Statistical Insights
Denunciar la contribución
Prim's Algorithm(G): 1. Choose a starting vertex s. 2. Mark s as visited. 3. Initialize an empty priority queue (min-heap) Q. 4. Add all edges incident to s to Q. 5. While Q is not empty: a. Extract the minimum-weight edge (u, v) from Q. b. If v is not visited: i. Mark v as visited. ii. Add (u, v) to the MST. iii. Add all edges incident to v that connect to unvisited vertices to Q. 6. Return the MST.

Traducido

Recomendar

3 ¿Cuáles son las ventajas del algoritmo de Prim?

El algoritmo de Prim tiene varias ventajas en comparación con otros métodos para encontrar MST, como el algoritmo de Kruskal o el algoritmo de Boruvka. El algoritmo de Prim es fácil de implementar y entender, especialmente si utiliza una estructura de datos simple como una matriz de adyacencia y un montón binario. Además, funciona de manera óptima para grafos densos, donde el número de aristas es cercano al máximo posible, ya que solo considera las aristas adyacentes a los vértices en el MST. Además, el algoritmo de Prim se puede modificar fácilmente para encontrar el segundo mejor MST, el MST de un subgrafo o el MST de un grafo con pesos negativos.

Añade tu opinión

4 ¿Cuáles son las desventajas del algoritmo de Prim?

Al utilizar el algoritmo de Prim, es importante ser consciente de sus inconvenientes. El algoritmo de Prim no es muy eficiente para gráficos dispersos, ya que todavía necesita verificar todos los bordes en la cola de prioridad. Además, requiere espacio adicional para almacenar los vértices visitados y la cola de prioridad, lo que puede ser significativo para gráficos grandes. Además, el algoritmo de Prim no es adecuado para la computación paralela o distribuida, ya que depende de un único vértice de origen y de una cola de prioridad global.

Añade tu opinión

5 Cómo prepararse para las preguntas del algoritmo de Prim

Si te estás preparando para una entrevista sobre estructuras de datos y algoritmos, es importante que te familiarices con el algoritmo de Prim. Para ello, revisa los conceptos básicos de los grafos, como los vértices, las aristas, los pesos, los ciclos y la conectividad. Además, practique la codificación del algoritmo de Prim en su lenguaje de programación preferido con diferentes estructuras de datos y casos de prueba. También es importante comparar y contrastar el algoritmo de Prim con otros algoritmos de MST, como los algoritmos de Kruskal o Boruvka, y comprender sus compensaciones y casos de uso. Además, aprende a modificar el algoritmo de Prim para resolver variaciones y extensiones del problema MST. Por último, piense en algunos escenarios del mundo real en los que puede ser útil encontrar un MST.

Añade tu opinión

6 Esto es lo que hay que tener en cuenta

Este es un espacio para compartir ejemplos, historias o ideas que no encajan en ninguna de las secciones anteriores. ¿Qué más te gustaría añadir?

Añade tu opinión

Federico Felizzi

Global HEOR Franchise Lead - Oncology
Denunciar la contribución
It is worth noting that Minimum Spanning Trees (MSTs) find applications in a wide range of areas. For instance, in the context of dependency parsing in NLP, there is a keen interest in identifying the Spanning Tree with the highest weight. MSTs have versatile applications that extend to logistics, circuit design, and have even proven valuable in predicting outbreaks during the COVID-19 pandemic. Additionally, they can be effectively employed in the allocation of resources, such as ICU units and medical equipment, to maximize public health outcomes.

Traducido

Recomendar
Jocelyn THIEBAUT

PhD in Theoretical Computer Science | Web Developer Passionate
Denunciar la contribución
Prim algorithm (as well as any algorithm computing MST of a graph) can be used to generate mazes. The idea is the following: consider a grid G of size n_1 x n_2, and put random weight on the edges. If you compute a MST T of G, you can represent your maze as follows: the cells are the vertices of G, and you have a wall between the cells u and v if the edge (u,v) is not an edge of T, otherwise, there is a corridor between these two cells. Note that depending of the algorithm you use, the "shape" of the maze might be different.

Traducido

Recomendar

Algoritmos

Seguir

Valorar este artículo

Hemos creado este artículo con la ayuda de la inteligencia artificial. ¿Qué te ha parecido?

Está genial Está regular

Denunciar este artículo

Ver todo

¿Cómo se utiliza el algoritmo de Prim para encontrar árboles de expansión mínimos?

1

2

3

4

5

6

1 Cómo funciona el algoritmo de Prim

2 Cómo implementar el algoritmo de Prim

3 ¿Cuáles son las ventajas del algoritmo de Prim?

4 ¿Cuáles son las desventajas del algoritmo de Prim?

5 Cómo prepararse para las preguntas del algoritmo de Prim

6 Esto es lo que hay que tener en cuenta

Algoritmos

Valorar este artículo

Gracias por tus comentarios

Más artículos sobre Algoritmos

Lecturas más relevantes

¿Cómo se utiliza el algoritmo de Prim para encontrar árboles de expansión mínimos?

1

2

3

4

5

6

1 Cómo funciona el algoritmo de Prim

2 Cómo implementar el algoritmo de Prim

3 ¿Cuáles son las ventajas del algoritmo de Prim?

4 ¿Cuáles son las desventajas del algoritmo de Prim?

5 Cómo prepararse para las preguntas del algoritmo de Prim

6 Esto es lo que hay que tener en cuenta

Algoritmos

Valorar este artículo

Gracias por tus comentarios

Explorar otras aptitudes