Prim's algorithm via Priority Queues to print the minimum spanning tree of an undirected graph

Question

Here's my attempt, I believe the runtime is O(V*(ElogE + log E)) since the while loop runs V times and it takes ElogE + log E to do the priority queue operations inside the loop.

class Edge implements Comparable<Edge> {
  T source;
  T destination;
  int weight;

  public Edge(T source, T destination, int weight) {
     this.source = source;
     this.destination = destination;
     this.weight = weight;
  }

  public int compareTo(Edge other) {
    return this.weight - other.weight;
    }
}

public void printMSTPrims(Map<T, List<Edge> > adjacencyList) {
        // Records all visited destinations.
        Set<T> visited = new HashSet<>();
        Queue<Edge> edges = new PriorityQueue<>();
        T currentNode = adjacencyList.entrySet().iterator().next().getKey();
        visited.add(currentNode);
        // Run until we've visited all vertices
        while (visited.size() < adjacencyList.size()) {
            
            // Take all edges from current node and add to the PQ.
            for (Edge edge: adjacencyList.get(currentNode)) {
                edges.add(edge);
            }

            // Pick the smallest edge to a destination node not already visited.
            Edge edge = edges.remove();
            while (!edges.isEmpty() && visited.contains(edge.destination)) {
                edge = edges.remove();
            }

            // Found an eligible edge, print its contents. This edge does not have to necessarily start from the currentNode.
            System.out.println(edge.source + "--" + edge.weight + "--" + edge.destination);
            // Go next to this destination vertex.
            currentNode = edge.destination;

            //Now that you've reached this edge as a destination, record it.
            visited.add(currentNode);
        }

}

PS. I assume the graph does not have self-loops and double-edges.

Answer 1

For who is not familiar with Prim's algorithm: it finds a minimum spanning tree for a weighted undirected graph.

My suggestions:

• Generics: the class Edge should be declared as Edge<T> or it won't compile as is. Or is it an inner class? Also the generic is missing in Comparable and the method compareTo.
• compareTo: typically, for primitive types is better to use <,>, and return -1,0 or 1. In your case, compareTo could overflow the integer with a negative weight. You can change it from:

  public int compareTo(Edge other) {
    return this.weight - other.weight;
  }
  

  To:

  public int compareTo(Edge other) {
    return Integer.compare(this.weight,other.weight);
  }
  

• addAll instead of for-loop: adding all edges to the queue can be done with addAll. From:

  for (Edge edge: adjacencyList.get(currentNode)) {
      edges.add(edge);
  }
  

  To:

  edges.addAll(adjacencyList.get(currentNode));
  

• Testing: the method printMSTPrims is hard to test. Would be better to have a method mstPrims that returns a result and then print it with another method. In that case, would be easier to test mstPrims.
• Naming: the name edges is a bit generic, an alternative can be edgeQueue or just queue.

Your final assumption:

PS. I assume the graph does not have loops and self-edges.

So a tree? A (connected) acyclic undirected graph is a tree. Anyway, looking at your method I don't think there should be problems even if there are cycles.

Answer 2

        for (Edge edge: adjacencyList.get(currentNode)) {
            edges.add(edge);
        }

This could more simply be

        edges.addAll(adjacencyList.get(currentNode));

A note on naming. I would find queue or edgeQueue to be just as generic as edges. I mean, we really don't care that it is a queue. Think about what the purpose of the queue is. In this case, it is to determine what edges to travel. So I would call it untraveled. I.e. I would name it like visited. Or possibly remainingEdges.

I would find neighbors or neighborsOf to be more explanatory than adjacencyList and better match visited. In general, I would try to avoid mixing meanings of something like List. In this case, you are referring to list in its graph theory meaning. But Java also has a List. Does your adjacency list (graph) have to be a Java List? No, it doesn't. Seeing as how it isn't a List but a Map.

    while (visited.size() < adjacencyList.size()) {

You might consider flipping this logic. Instead of building a visited list, start with a destinations list:

    Set<T> remaining = adjacencyList.keySet();

with

    while (!remaining.isEmpty()) {

and

        while (!edges.isEmpty() && !remaining.contains(edge.destination)) {

Note that this also allows you to say

    T currentNode = remaining.iterator().next();
    remaining.remove(currentNode);

which is somewhat simpler than your current form.

If you are using remainingEdges, you could call this remainingDestinations or remainingNodes or similar.

A benefit of this is that it localizes the relationship between remaining and adjacencyList to just one place. So if you later wanted to remove that relationship, you could do so easily. And in the more common case of reading the code, you would only need to look one place to see it. The current code is confusing in that there is no particular reason why the collection of things to visit should be the same size as the adjacency list. That's not a a property of the algorithm but of your implementation.

Consider a case where we have a global adjacency list and a local list of places to visit. You can't easily adjust your method to cover that directly. But if we create a remaining collection, then we can. So why not create it now? It simplifies the current logic and leaves the method more expandable.