[Java] Prim algorithm to find Minimum Spanning Tree in a graph

The minimum spanning tree (MST) is a subset of all edges in a weighted, undirected, connected graph such that the resulting graph is still connected and the sum of all edge weights is minimal.

If we are not given a list of edges, but only a list of vertices and a formula to calculate the edge weight given two graph nodes, we can run a preprocessing step to generate ALL possible edges between ALL graph nodes and calculate their weight in O(V^2).

Then, starting from a random node, we greedily choose one reachable vertex which has minimal distance from the current node. We continue exploring until all graph nodes have been touched.

There might be multiple valid MSTs for a given graph, this algorithm will return one of them.

We use a queue sorted by weight to determine which edge (and therefore node) to visit next, this ensures that if a node is reachable via multiple edges, we always pick the smallest weight for it. Since the graph is fully connected, we are ensured eventually we will have picked ONE edge between each node in the graph, and the sum of weight of all the chosen edges is minimal.

This runs using O(E) space since we might add all edges to the queue and O(E log(E)) time since for each edge we add to the queue we pay the O(log(E)) cost of insert and remove operation.

If the graph was NOT connected, this will NOT return the MST, only the MST for the connected component where the chosen start node resides. We could adapt the algorithm to verify whether there are extra nodes not yet visited, and repeat the processing for each until we have created a MST for each connected component in the graph.

In case the graph is not conencted, an alternatve can also be Kruskal's algorithm.

You can find my implementation of primMinimumSpanningTree on my Gist along with some tests in PrimMSTJTests.