Live briefing
Everything about Prim's algorithm
Method for finding minimum spanning trees
In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Prim's algorithmA 5-minute orientation
- Skim a recent paper: A tool-path planning method used in computer controlled optical surfacing based on improved prim algorithmInfluential work since 2022
- Pick up a classic book: Discrete and combinatorial mathematicsThe most-reprinted book on the subject
- Read the landmark paper: A Prim–Dijkstra Algorithm for Multihop Calibration of Networked Embedded SystemsCited 19 times
- Go sideways: Kruskal's algorithmA closely related topic
- Go sideways: Borůvka's algorithmA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
A Prim–Dijkstra Algorithm for Multihop Calibration of Networked Embedded Systems
Prim Algorithm Approach to Improving Local Access Network in Rural Areas
The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm
A Prim Minimum Spanning Tree Algorithm for Directed Graph
A Random PRIM Based Algorithm for Interpretable Classification and Advanced Subgroup Discovery
Optimized Traveling Route Scheme based on Improved Prim Algorithm
Optimization of Highway Construction Based on Prim Algorithm
K-Means Clustering Algorithm Based on Prim Improvement
🆕 Influential since 2022
A tool-path planning method used in computer controlled optical surfacing based on improved prim algorithm
Increasing package delivery efficiency through the application of the prim algorithm to find the shortest route on the expedition route
Optimizing MRT Pathways between Jakarta Malls: Comparative Study of Kruskal and Prim Algorithms
Application of Prim Algorithm to an Electricity Network in Cimahi
Optimization Of The Water Distribution Network of Regional Water Utility Company (PDAM) Using Prim Algorithm
📚 Books worth reading
Discrete and combinatorial mathematicsRalph P. Grimaldi · 1985
Data structures and algorithm analysis in CMark Allen Weiss · 1993
The Elements of Statistical LearningTrevor Hastie, Robert Tibshirani · 2001
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999
Data structures and algorithms in JavaAdam Drozdek · 2001
Computer algorithmsEllis Horowitz · 1997
Fundamentals of data structures in CEllis Horowitz · 1993
Introductory discrete mathematicsV. K. Balakrishnan · 1991
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Kruskal's algorithm Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree.…
- Borůvka's algorithm Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not…
- Reverse-delete algorithm The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first…
- Minimum spanning tree In graph theory, a minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph…
- Dijkstra's algorithm Dijkstra's algorithm (/ˈdaɪk.strəz/, DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent…
- Parallel algorithms for minimum spanning trees In graph theory a minimum spanning tree (MST) T {\displaystyle T} of a graph G = ( V , E ) {\displaystyle G=(V,E)} with | V | = n {\displaystyle |V|=n}…
- Expected linear time MST algorithm The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices…
- Spanning tree In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of…