How to Implement Prim’s Algorithm for Minimum Spanning Tree

Introduction

Prim’s Algorithm is a greedy technique used to find a minimum spanning tree by connecting all the nodes in a weighted, undirected graph using the least total edge weight, without creating any loops.

Understanding the Minimum Spanning Tree

A spanning tree links all the nodes in a graph using a subset of its edges, ensuring that there are no loops. When the sum of the edge weights in such a tree is the lowest among all possible spanning trees, it is called a Minimum Spanning Tree. In a graph with n vertices, every spanning tree includes exactly n - 1 edges.

Core Idea Behind Prim’s Algorithm

Prim’s Algorithm makes the spanning tree grow one edge at a time. It starts from any chosen node and repeatedly adds the smallest edge that connects a visited vertex to an unvisited one. It continues until every vertex has been added to the tree.

Steps involved:

• Begin with one starting vertex.
• Mark this vertex as part of the MST.
• At each step, among all edges from the tree to non-tree vertices, choose the smallest.
• Repeat until all vertices are connected.

Java Implementation

The following is an original Java program that uses Prim’s Algorithm with a graph represented by an adjacency matrix. The algorithm keeps track of the lowest-cost edges using an array and builds the MST using a simple greedy approach.

public class PrimTree {

    private static final int MAX = Integer.MAX_VALUE;

    public void constructTree(int[][] costMatrix) {
        int nArr = costMatrix.length;
        boolean[] inTree = new boolean[nArr];
        int[] minEdg = new int[nArr];
        int[] connectingVertex = new int[nArr];

        Arrays.fill(minEdg, MAX);
        minEdg[0] = 0;
        connectingVertex[0] = -1;

        for (int i = 0; i < nArr - 1; i++) {
            int u = chooseVertex(minEdg, inTree);
            inTree[u] = true;

            for (int v = 0; v < nArr; v++) {
                if (costMatrix[u][v] != 0 && !inTree[v] && costMatrix[u][v] < minEdg[v]) {
                    minEdg[v] = costMatrix[u][v];
                    connectingVertex[v] = u;
                }
            }
        }

        displayTree(connectingVertex, costMatrix);
    }

    private int chooseVertex(int[] minEdge, boolean[] inTr) {
        int min = MAX;
        int index = -1;

        for (int i = 0; i < minEdge.length; i++) {
            if (!inTr[i] && minEdge[i] < min) {
                min = minEdge[i];
                index = i;
            }
        }

        return index;
    }

    private void displayTree(int[] parent, int[][] graph) {
        for (int i = 1; i < graph.length; i++) {
            System.out.println(parent[i] + " -> " + i + "  cost: " + graph[i][parent[i]]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 3, 0, 0, 6, 0},
            {3, 0, 1, 0, 2, 0},
            {0, 1, 0, 4, 0, 5},
            {0, 0, 4, 0, 0, 7},
            {6, 2, 0, 0, 0, 8},
            {0, 0, 5, 7, 8, 0}
        };

        PrimTree tree = new PrimTree();
        tree.constructTree(graph);
    }
}

Example Output

Using the graph above, the program may generate output similar to the following:

Edges in the Minimum Spanning Tree:
0 -> 1  cost: 3
1 -> 2  cost: 1
2 -> 3  cost: 4
1 -> 4  cost: 2
2 -> 5  cost: 5

This output shows which vertices are connected in the MST and the weight of each edge chosen.

Performance Notes

This approach runs in O(V²) time, where V is the number of vertices, due to the use of a linear search to select the minimum edge. For larger graphs, the efficiency can be significantly improved by using a priority queue or min-heap, reducing the time complexity to O(E log V) when combined with adjacency lists.

Conclusion

Prim’s Algorithm offers a straightforward and effective strategy for building a Minimum Spanning Tree. It ensures that every step contributes to the global minimum by choosing the next best local edge. Though its basic form is best suited for small or dense graphs, it serves as a powerful foundation for network optimization and is widely used in real-world applications like communication and transport systems.

You can find the example code on Github.