Prim's algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree by repeatedly adding the least-weight edge connecting the growing tree to a new vertex.

Minimum spanning tree: A minimum spanning tree is a least-total-weight set of edges connecting every vertex of a connected weighted graph without cycles. This is the structure Prim's algorithm constructs.
Kruskal's algorithm: Kruskal's algorithm builds a minimum spanning forest by adding edges in increasing weight order while avoiding cycles. Unlike Prim's, it selects globally light edges rather than extending one growing tree.
Network design: Network design chooses connections and capacities to meet communication, transport, or utility requirements. A minimum spanning tree can connect sites while minimizing total link cost.
Vojtěch Jarník: Vojtěch Jarník was a Czech mathematician who published a greedy method for constructing a minimum spanning tree in 1930. His earlier publication established the method later widely known by Prim's name.
Cut property: The cut property states that a minimum-weight edge crossing a graph cut is safe to include in a minimum spanning tree. It proves each lightest frontier edge can be added without losing optimality.
Borůvka's algorithm: Borůvka's algorithm builds a minimum spanning forest by repeatedly joining components through their cheapest outgoing edges. It grows many components at once instead of maintaining Prim's single-tree frontier.
VLSI design: VLSI design creates integrated circuits containing very large numbers of electronic components. Spanning-tree methods help estimate or reduce wiring needed to connect circuit elements.
Robert C. Prim: Robert C. Prim was an American mathematician and computer scientist who published a minimum spanning tree algorithm in 1957. His account helped make the algorithm's current English name standard.
Priority queue: A priority queue is a data structure that retrieves an item with the highest or lowest priority efficiently. It efficiently selects the cheapest edge or vertex on the tree's frontier.
Dijkstra's algorithm: Dijkstra's algorithm finds shortest paths from one source in a graph with nonnegative edge weights. Its similar greedy selection rule solves shortest paths, not the minimum spanning tree problem.

Linked from 4 pages