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

Find an undirected MST directly from a dense symmetric matrix. Null is no edge; zero and negative costs are real usable edges, and diagonal values do not connect new vertices.

Converting every matrix entry to an edge list duplicates dense representation work. Prim can retain one best crossing cost per unvisited vertex, selecting and updating that compact frontier row by row.

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.

Dense Prim stores the cheapest crossing edge for each unvisited vertex. Each iteration selects the minimum frontier cost, then relaxes that vertex's entire row. An unreachable minimum means disconnection. Negative and zero weights remain valid; null is absence, so a numeric sentinel must not conflate them. Final O(V²) time and O(V) space.

Absence must not be represented by zero because zero can be the cheapest valid connection:

import java.util.*;

class Example {
    public static void main(String[] args) {
        Long absent = null;
        Long freeConnection = 0L;
        Long negativeConnection = -2L;
        assert absent == null;
        assert freeConnection != null;
        assert negativeConnection < freeConnection;
    }
}

A minimum frontier value that is absent indicates disconnection, while zero must be accepted normally. Shape and symmetry validation happen before ignoring diagonal entries, so malformed matrices cannot slip through an early empty/singleton answer.

Choosing a matrix or an edge list

Array-frontier Prim is a useful dense-graph counterpart to sorting sparse edges. O(V²) matrix access and O(V) auxiliary frontier space avoid a large heap or extra edge-list copy.

Require a square, symmetric Long matrix (null means no edge), otherwise IllegalArgumentException. Validate symmetry before ignoring diagonal values. Return the minimum spanning-tree total or null if disconnected. Empty matrix returns 0L. Prototype may convert to an edge list and apply an MST algorithm.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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