Prim minimum spanning trees

A lab has a cost matrix for wiring its workstations together. It needs minimum total connection cost, as in Kruskal, but most pairs already have quotes in the matrix. Turning every quote into a separate sorted edge record adds work and storage.

Prim grows one connected component instead. For every outside workstation, it remembers the cheapest single cable connecting it to that component, then chooses the best next connection.

Working directly from the cable quote matrix

Dense Prim maintains each unselected vertex's cheapest edge into the selected set. Repeatedly choose the lowest frontier cost, add that vertex, then improve remaining frontier entries using its matrix row. This grows a tree directly instead of sorting every matrix edge.

Growing the cheapest connection frontier

Quotes 0–1:2, 0–2:8, and 1–2:1 first connect 1 for two. Once 1 is inside the component, workstation 2 can connect for one rather than eight. Its frontier value becomes one, not three: Prim stores an attachment edge, not the route cost from 0. The total installation cost becomes three after accepting both links.

std::vector<std::optional<Int>> frontier(costs.size());
frontier[0]=0; // root contributes no edge cost

Choosing a matrix or an edge list

An absent frontier means disconnected, not expensive. Zero and negative edge costs must remain legitimate candidates. The diagonal does not contribute an edge to the tree, but matrix shape and symmetry are validated before ignoring diagonal values. Copying matrix rows unnecessarily doubles already quadratic storage; retain const references and use O(V) extra arrays. Scanning V frontier entries V times gives O(V²) work, which is appropriate for dense input. A sparse heap representation addresses a different storage choice.

Scanning the frontier and a row for each of V selections costs O(V²) time and O(V) auxiliary storage beyond the matrix. Converting the matrix to an edge list and sorting it adds candidate storage and logarithmic sorting work. For a sparse edge list, Kruskal or heap-based Prim may be a better representation fit.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

A missing quote and a genuine zero-cost cable must remain distinguishable throughout the matrix scan.