Today, I introduce you to Prim’s Algorithm Minimum Spanning Tree in Java and how to use it finding the minimum spanning tree. Sometimes, Prim’s Algorithm is called Minimum Spanning Tree (MST) algorithm, it takes a graph as input and produces a MST tree.
Prim’s Algorithm Minimum Spanning Tree in Java
What’s Prim’s Algorithm?
Prim’s algorithm is a greedy algorithm and it is used to find a minimum spanning tree for a weighted undirected graph.
Minimum Spanning Tree
A MST tree has some properties:
- It includes all vertices of graph.
- It has a minimum possible number of edges of graph.
Please have a look at this picture. You will see a MST tree that is a part of graph.
How Prim’s algorithm works
In this post, we will use a graph in the above picture as input for this algorithm and this grap is represented in the adjacent matrix. In general, we start from any one vertex then add adjacent vertex with the edge that is the lowest weight until we reach to all vertices of the graph. Implementation of the algorithm follows the steps:
- Create MST like an array to store all vertices of the graph later. Then initialize the first element of this array is a random vertex of the adjacent matrix.
- Find all the edges of vertices in MST tree with new vertices in graph. Find the edge is with the minimum weight then add a new vertex in MST tree.
- Keep repeating step 2 until we reach all vertices of graph. The we get a MST tree.
Implementation of Prim’s algorithm in Java
Here, we reuse the source code of the previous post to implement Prim’s Algorithm Minimum Spanning Tree in Java. we just add some methods for algorithm implementation.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
// Simple program implements a Graph in adjacency matrix import java.util.*; class Graph { private int size; private int adjMatrix[][]; Graph(int s){ this.size = s; adjMatrix = new int[size][size]; } public int[][] getAdjMatrix(){ return adjMatrix; } // adds a new edge to the graph public void addEdge(int i, int j, int weighted) { adjMatrix[i][j] = weighted; adjMatrix[j][i] = weighted; } // remove a edge to the graph public void removeEdge(int i, int j) { adjMatrix[i][j] = -1; adjMatrix[j][i] = -1; } // get graph size public int size() { return this.size; } // Displays the adjancency matrix of graph. public String toString() { StringBuilder s = new StringBuilder(); for (int i = 0; i < size; i++) { s.append(i + ": "); for (int j : adjMatrix[i]) { s.append((j) + " "); } s.append("\n"); } return s.toString(); } //find the vertex with minimum weight which is not included in MST int getMinVertexIndex(Boolean [] mstArray, int [] indexArray){ int minIndex = Integer.MAX_VALUE; int index = -1; for (int i = 0; i <size ; i++) { if(mstArray[i]==false && minIndex>indexArray[i]){ minIndex = indexArray[i]; index = i; } } return index; } // Method create a MST of graph, //it accepts a graph in adjacency matrix. // 2d array matrix is only contain values that is not zero int[] primMST(int matrix[][]) { //Store Minimum Spanning Tree (MST) int resultMst[] = new int[size]; //Store minimum weighted value of vertices int wData[] = new int[size]; //Array marks a vertex in MST (parrent array above) or not. Boolean mstArray[] = new Boolean[size]; // Initialize all data of vertices as INFINITE // and elements of weighted array to false for (int i = 0; i < size; i++) { wData[i] = Integer.MAX_VALUE; mstArray[i] = false; } // Put first vertex into array and it is considered is root node // so its weighted data is set to 0 //and it doesn't have any parent then set its parent = -1 wData[0] = 0; resultMst[0] = -1; // Create MST, obviously MST's size is equal to graph's size for (int i = 0; i < size - 1; i++) { // Pick thd minimum vertex from the set of vertices // not yet included in MST int minIdex = getMinVertexIndex(mstArray, wData); // Add the picked vertex to the MST Set mstArray[minIdex] = true; // Update key value and parent index of the adjacent // vertices of the picked vertex. Consider only those // vertices which are not yet included in MST for (int v = 0; v < size; v++) // matrix[minIdex][v] is not zero // only process vertex that is not put in mstArray // Update resultMst and wData if matrix[minIdex][v] is smaller than wData[v] if (matrix[minIdex][v] != 0 && mstArray[v] == false && matrix[minIdex][v] < wData[v]) { resultMst[v] = minIdex; wData[v] = matrix[minIdex][v]; } } return resultMst; } } // Main class public class Main { public static void main(String args[]) { // create new graph instance Graph g = new Graph(4); // the create an array of vertices int[] vertices = new int[g.size()]; vertices[0] = 20; vertices[1] = 30; vertices[2] = 10; vertices[3] = 40; // sort vertices array // then use binary search algorthim to get the index of vertices Arrays.sort(vertices); System.out.println("Sorted vertices array: " +Arrays.toString(vertices)); int index20 = Arrays.binarySearch(vertices,20); int index10 = Arrays.binarySearch(vertices,10); int index30 = Arrays.binarySearch(vertices,30); int index40 = Arrays.binarySearch(vertices,40); //Now we create a graph from the corresponding indexes of vertices, // edges are added. g.addEdge(index10, index20,3); g.addEdge(index10, index40,1); g.addEdge(index20, index30,4); g.addEdge(index20, index40,2); g.addEdge(index30, index40,6); // print the graph. System.out.println("Here is the graph:\n" + g.toString()); int[][] graph = g.getAdjMatrix(); int[] mst = g.primMST(g.getAdjMatrix()); System.out.println("Edge(vertex<->vertex) \t\tWeight"); for (int i = 1; i < g.size(); i++) System.out.println("\t"+vertices[mst[i]] + " - " + vertices[i] + "\t\t\t" + graph[i][mst[i]]); } } |
Here is output of the above program
Time Complexity:
Time Complexity of the above program is O(V2). Because we are using a graph in adjacency matrix
That’s all about Prim’s Algorithm Minimum Spanning Tree in Java.
