is my Prim's MST implementation terse enough?

Question

I did research because I want to learn Kruskal's and Prim's MSTs. I did research and after a solid understanding, I went to my textbook and got their libraries:

• https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Edge.java.html

• https://algs4.cs.princeton.edu/43mst/EdgeWeightedGraph.java.html

Here is my code, I've done some tests and it checks out on my end. I struggled a lot with finding an end point when inputted a start point, since when there is a dead end you kind of back track in the priority queue to the next best option.

import edu.princeton.cs.algs4.EdgeWeightedGraph;
import edu.princeton.cs.algs4.Edge;
import java.util.PriorityQueue;
import java.util.Queue;
public class MinimumSpanningForest {
 public static EdgeWeightedGraph g;
 public static boolean[] visited;
 public static Queue<Edge> pq = new PriorityQueue<Edge>();
 public static void edgeCompareTest() {
 Edge one = new Edge(1,2,2.0);
 Edge anotherOne = new Edge(1,3,4.0);
 Edge seven = new Edge(7,1,2.0);
 Edge anotherSeven = new Edge(7,4,1.0);
 System.out.println("one compared to one: " + one.compareTo(one));
 System.out.println("one compared to another one: " + one.compareTo(anotherOne));
 System.out.println("one compared to seven: " + one.compareTo(seven));
 System.out.println("seven compared to one: " + seven.compareTo(one));
 System.out.println("one compared to null: " + one.compareTo(null));
 }
 public static void main(String[] args) {
 g = new EdgeWeightedGraph(5,5);
// g.addEdge(new Edge(0,1,0.3));
// g.addEdge(new Edge(0,2,0.5));
// g.addEdge(new Edge(2,3,1.2));
// g.addEdge(new Edge(1,4,0.8));
 System.out.println(g);
 prim(g);
 //Queue<Edge> queue = new PriorityQueue<>((e1 , e2) -> e1.weight().compareTo(e2.weight()));
 for (int i = 0; i < g.E(); i++) {
 for(Edge e : g.adj(i)) {
 pq.add(e);
 }
 }
 }
 private static void qEdges(int vertex) {
 visited[vertex] = true;
 for (Edge edge : g.adj(vertex)) {
 if(!visited[edge.other(vertex)]) {
 pq.add(edge);
 }
 }
 }
 public static void prim(EdgeWeightedGraph g) {
 visited = new boolean[g.V()];
 int e = g.V() - 1;
 int edgeCount;
 double mstCost;
 int otherPt = 0;
 edgeCount = 0;
 mstCost = 0;
 Edge[] mstEdges = new Edge[e];
 qEdges(otherPt);
 while(!pq.isEmpty() && edgeCount != e) {
 Edge edge = pq.remove();
 otherPt = (!visited[edge.either()]) ? edge.either() : edge.other(edge.either());
 if(visited[otherPt]) {
 continue;
 }
 mstEdges[edgeCount++] = edge;
 mstCost += edge.weight();
 qEdges(otherPt);
 }
 if (edgeCount != mstEdges.length) {
 System.out.println("No MST exists!");
 } else {
 System.out.println("There is a MST in the following order of edges: ");
 for(Edge edge : mstEdges) {
 System.out.println(edge);
 }
 System.out.println("With a cost of " + mstCost);
 }
 }
 public static void kruskal(EdgeWeightedGraph g) {
 }
}

I did not do Kruskal's yet, but I figured that it would be best to make sure Prim's doesn't have any glaring fixes y'all would advise before I go ahead to Kruskals. Thanks.

• vnp: "No MST exists!" - is it possible?
• William Golovlev: @vnp yes it is if the graph doesn't use all nodes/vertices. It cannot be disconnected.

Answer 1

Seeing you hyperlinked Princeton Algorithms, 4th Ed. resources, I assume you know how to view their take of Prim's.
I do not understand your concern about terseness.

There is one striking difference between the code you present for review and that of edu.princeton.cs.algs4.Edge and EdgeWeightedGraph it uses:
Theirs is documented using the standard mechanism -
Everything public carries a doc comment. Even accessors.
→ Follow, or use something better.

For a class MinimumSpanningForest, a static member graph looks odd.
All three static member declarations in combination look state of a single invocation. Seeing kruskal() in addition to prim(), an invocation of some graph algorithm or forest~?
→ There should probably be an interface both Prim&Kruskal implement, each with its own per instance state.
A common base class could highlight commonalities.

(Finding Jarník/Prim/Dijkstra's algorithm the only one spelled out in a class MinimumSpanningForest is odd as it originally constructs a single spanning tree (containing the CC of the the initial node chosen) while Kruskal's "naturally" arrives at the forest.)

I find the high-level description of Prim's easier to recognise in your take, while Princeton's may store less elements in the PQ.

I like names chosen for the purpose of what they name:
shortestEdges instead of pq,
vertex or toAdd instead of otherPt (while I can sort of see how it got "other" (would have preferred "unvisited"), what is "Pt" for?)
qEdges is overdoing terseness - enqueueEdges would do nicely.
(With a development tool supporting renaming, you don't need to type it that way.)
(I don't think I'd qualify any name local to prim() with mst.)
I'd comment why both vertices connected by an edge from the queue may be marked visited when only edges with one unvisited vertex are enqueued.

I like concerns separated:
I'd rather have an MST/MSF implementation return sets of edges, and specify&implement printing elsewhere.
To this end, and seeing the number of edges might not reach #vertices-1 when \$g\$ is not connected, I'd collect edges in a List.