Prims

Prims is a term commonly associated with Prim's algorithm, a greedy method for computing a minimum spanning tree (MST) of a connected weighted undirected graph. The algorithm is named after Robert C. Prim, who described it in 1957. It starts from an arbitrary vertex and repeatedly adds the lightest edge that connects a vertex inside the growing tree to a vertex outside.

Two standard implementations exist. A simple version uses an adjacency matrix and maintains a set of included vertices, resulting in a time complexity of O(V^2). A more efficient approach uses a priority queue to select the next edge and achieves O(E log V) time for a graph with V vertices and E edges. Space usage is typically O(V) for tracking the best connections and predecessors.

Prim's algorithm has the property that, for a connected graph, it produces a minimum spanning tree. If all edge weights are distinct, the MST is unique; otherwise, multiple different MSTs may exist. The algorithm is closely related to Kruskal's algorithm, which constructs an MST by sorting all edges and adding safe edges in increasing order.

Applications of Prim's algorithm include network design, such as laying out cables or pipelines, and it is frequently taught as a foundational technique in graph theory. It can also serve as a preprocessing step in various optimization and clustering problems.

History and usage: the method was introduced by Robert C. Prim in 1957, and it has since become a standard tool in algorithm textbooks and software libraries. See also: minimum spanning tree, Kruskal's algorithm.