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

Prim grows a connected component by its cheapest outgoing edge. Each unselected vertex stores the cheapest single connection into the selected set, rather than a total path distance.

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.

selected := []bool{true, true, false}
best := []int{0, 2, 8}
rowFromOne := []int{2, 0, 1}
for vertex, weight := range rowFromOne {
	if !selected[vertex] && weight < best[vertex] {
		best[vertex] = weight // A single attachment edge, not a route sum.
	}
}
fmt.Println(best) // [0 2 1]

Choosing a matrix or an edge list

For a dense matrix, scanning a length-V frontier for each selection gives O(V²) time and O(V) extra space. An unreachable frontier means disconnected. Zero and negative edges are real costs; a nil pointer distinctly means no edge. Validate symmetry before relying on an undirected model. Build private working state. The Go API uses nil for absence and assumes finite cost arithmetic fits int.

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.

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