Prim’s Minimum Spanning Tree Implementation

Graph is a non linear data structure that has nodes and edges. Minimum Spanning Tree is a set of edges in an undirected weighted graph that connects all the vertices with no cycles and minimum total edge weight. When number of edges to vertices is high, Prim’s algorithm is preferred over Kruskal’s. This content is about implementing Prim’s algorithm for undirected weighted graph.

First step is to create two classes GraphNode and Edge.

class GraphNode {
    String alias;                     // it is a label of node
    Object data;                      // data that is stored in node
    
    GraphNode(String alias, Object data) {
       this.alias = alias;
       this.data = data;
    }
}class Edge {
    GraphNode src;                  // edge's origin
    GraphNode dest;                 // edge's end
    Integer cost;                   // cost of the edge     
     
    Edge(GraphNode src, GraphNode dest, Integer cost) {
        this.src = src;
        this.dest = dest;
        this.cost = cost;
    }
}

A class named Graph is created that will have methods and several data structures. For ease, Java’s library guava is used for various Sets operations.

private HashSet<HashSet<String>> pUniversal = new HashSet<>();private ArrayList<Edge> primEdges = new ArrayList<>();
private ArrayList<Edge> tempEdges = new ArrayList<>();
private ArrayList<Edge> operationalEdges;private String selectedNode = "";

Following are the methods in class Graph:

public void addEdge(GraphNode src,GraphNode dest,Integer cost) {    

    universalNodes.add(Sets.newHashSet(src.alias));
    universalNodes.add(Sets.newHashSet(dest.alias));
    primEdges.add(new Edge(src, dest, cost));
    selectedNode = src.alias;}public ArrayList<Edge> primMST() {    totalCost = 0;
    pUniversal = new HashSet<>(universalNodes);
    operationalEdges = new ArrayList<>();
    ArrayList<Edge> MSTEdges = new ArrayList<>();
    int edgesLimit = pUniversal.size() - 1;
    tempEdges.addAll(primEdges);
    while (MSTEdges.size() != edgesLimit) {
        getSelectedEdges();
        for (int i = 0; i < operationalEdges.size(); i++) {
            Edge edge = operationalEdges.get(i);
            if (isAcyclic(edge.src.alias, edge.dest.alias, false)) {
                pUniversal.add(Sets.newHashSet(Sets.union(subSet1,
                               subSet2)));
                pUniversal.remove(subSet1);
                pUniversal.remove(subSet2);
                MSTEdges.add(edge);
                totalCost += edge.cost;
                selectedNode = edge.dest.alias;
                operationalEdges.remove(edge);
                break;
            }
        }
    }
    return MSTEdges;
}private void getSelectedEdges() {
    for (int i = 0; i < tempEdges.size(); i++) {
        Edge target = tempEdges.get(i);
        if (target.src.alias.equals(selectedNode)) {
            operationalEdges.add(target);
        } else if (target.dest.alias.equals(selectedNode)) {
            GraphNode dest = target.src;
            target.src = target.dest;
            target.dest = dest;
            operationalEdges.add(target);
        }
    }
    tempEdges.removeAll(operationalEdges);
    operationalEdges.sort(Comparator.comparing(edge -> edge.cost));
}public boolean isAcyclic(String srcAlias, String destAlias) {
    subSet1 = new HashSet<>();
    subSet2 = new HashSet<>();
    HashSet<HashSet<String>> targetSet;
    targetSet = pUniversal;

    for (HashSet<String> subSet : targetSet) {
        if (subSet.contains(srcAlias)) subSet1 = subSet;
        if (subSet.contains(destAlias)) subSet2 = subSet;
        if (subSet1 == subSet2) return false;
    }
    return true;
}

Description of all three methods:

A)addEdge(GraphNode src, GraphNode dest, Integer cost):

This method has 3 arguments that denotes source, destination and cost of the edge. It adds edge to the list named primEdges . Along with this, when edges are being added, the nodes are appended as Set in a Set called universalNodes. Hereby, primEdges contains list of all the edges that a graph has, whereas universalNodes contains all unique node sets. For an instance, universalNodes would look like:

B)getSelectedEdges():

This method creates/appends edges to the list named ‘operationalEdges’. All edges that have selected node, as either src or dest , are fetched. If the selected node is dest then edge undergoes swapping of src and dest. As it is undirected graph, swapping does not make any difference in finding out Minimum Spanning Tree. At last, list ‘operationalEdges’ is sorted in ascending order as per the cost of edges.

C)isAcyclic(String srcAlias, String destAlias):

Firstly, subSet1 and subSet2 are created. Loop iterates through pUniversal and updates aforementioned two sets when src or dest node is found. If they belong in the same set then that edge is responsible for forming a cycle and hence the method will return false, otherwise true.

D)primMST():

When building Minimum Spanning Tree, this is the method that is to be called in programming. If the graph has n nodes then minimum spanning tree will contain n-1 edges, so accordingly loop will break when size of ‘MSTEdges’ list reaches upto n-1. This loop is iterated after getSelectedEdges() method. Hence, initially first edge will be targeted to check whether or not it forms a cycle in Spanning Tree after appending. If it does not form a cycle, it will be appended, otherwise next edge in the list will be targeted.

Fig. 1 : Targeted graph for finding minimum spanning tree

Following lines of code builds a graph mentioned in Fig. 1:

// Create object of class Graph
Graph testGraph = newGraph();
Graph.MINIMUM_SPANNING_TREE_ALGORITHM = 1;// here second argument is data for node, it is optional and not
// required currently for spanning tree. Data can be anything.
// String, integer, custom class object, etc.// Create objects of class GraphNode
GraphNode A = new GraphNode("A", "Data for node A");
GraphNode B = new GraphNode("B", "Data for node B");
GraphNode C = new GraphNode("C", "Data for node C");
.
.
.
.
GraphNode J = new GraphNode("J", "Data for node J");// Add edges to the testGraph, as per the above image (Fig.1)
testGraph.addEdge(A, B, 3);
testGraph.addEdge(E, A, 9);
testGraph.addEdge(A, D, 6);
.
.
.
.
testGraph.addEdge(E, F, 8);// Print MSTEdges, the list that has all the edges and lastly, total // cost of minimum spanning tree
for (Edge edge: testGraph.primMST()) {
    System.out.println(edge.src.alias + " - " + edge.dest.alias + "
                                                   : " + edge.cost);
}
System.out.println(testGraph.getTotalCost());

Final Result with total cost of 38 units :

Fig. 2: Minimum Spanning Tree

Link to the entire program: Graph.java