Earlier we have seen what is Prim’s algorithm is and how it works. In this article we will see its implementation using adjacency matrix.

We strongly recommend to read – prim’s algorithm and how it works.

**Example**:

**Implementation – Adjacency Matrix**

- Create mst[] to keep track of vertices included in MST.
- Create key[] to keep track of key value for each vertex. Which vertex will be included next into MST will be decided based on the key value.
- Initialize key for all vertices as MAX_VAL except the first vertex for which key will 0. (Start from first vertex).
- While(all the vertices are not in MST).
- Get the vertex with the minimum key. Say its vertex
.*u* - Include this vertex in MST and mark in mst[
] = true.*u* - Iterate through all the adjacent vertices of above vertex
and update the keys if adjacent vertex is not already part of mst[].*u*

- Get the vertex with the minimum key. Say its vertex
- We will use Result object to store the result of each vertex. Result object will store 2 information’s.
- First the parent vertex, means from which vertex you can visit this vertex. Example if for vertex
**v**, you have included edge**u-v**in mst[] then vertex**u**will be the parent vertex. - Second weight of edge u-v. If you add all these weights for all the vertices in mst[] then you will get Minimum spanning tree weight.

- First the parent vertex, means from which vertex you can visit this vertex. Example if for vertex
- See the code for more understanding. Go through the commented description.

**Time Complexity**: O(|V|^{2}).

Please see the animation below for better understanding.

**Java Code: **

public class PrimAlgorithmAdjacencyMatrix { | |

static class Graph{ | |

int vertices; | |

int matrix[][]; | |

public Graph(int vertex) { | |

this.vertices = vertex; | |

matrix = new int[vertex][vertex]; | |

} | |

public void addEdge(int source, int destination, int weight) { | |

//add edge | |

matrix[source][destination]=weight; | |

//add back edge for undirected graph | |

matrix[destination][source] = weight; | |

} | |

//get the vertex with minimum key which is not included in MST | |

int getMinimumVertex(boolean [] mst, int [] key){ | |

int minKey = Integer.MAX_VALUE; | |

int vertex = –1; | |

for (int i = 0; i <vertices ; i++) { | |

if(mst[i]==false && minKey>key[i]){ | |

minKey = key[i]; | |

vertex = i; | |

} | |

} | |

return vertex; | |

} | |

class ResultSet{ | |

// will store the vertex(parent) from which the current vertex will reached | |

int parent; | |

// will store the weight for printing the MST weight | |

int weight; | |

} | |

public void primMST(){ | |

boolean[] mst = new boolean[vertices]; | |

ResultSet[] resultSet = new ResultSet[vertices]; | |

int [] key = new int[vertices]; | |

//Initialize all the keys to infinity and | |

//initialize resultSet for all the vertices | |

for (int i = 0; i <vertices ; i++) { | |

key[i] = Integer.MAX_VALUE; | |

resultSet[i] = new ResultSet(); | |

} | |

//start from the vertex 0 | |

key[0] = 0; | |

resultSet[0] = new ResultSet(); | |

resultSet[0].parent = –1; | |

//create MST | |

for (int i = 0; i <vertices ; i++) { | |

//get the vertex with the minimum key | |

int vertex = getMinimumVertex(mst, key); | |

//include this vertex in MST | |

mst[vertex] = true; | |

//iterate through all the adjacent vertices of above vertex and update the keys | |

for (int j = 0; j <vertices ; j++) { | |

//check of the edge | |

if(matrix[vertex][j]>0){ | |

//check if this vertex 'j' already in mst and | |

//if no then check if key needs an update or not | |

if(mst[j]==false && matrix[vertex][j]<key[j]){ | |

//update the key | |

key[j] = matrix[vertex][j]; | |

//update the result set | |

resultSet[j].parent = vertex; | |

resultSet[j].weight = key[j]; | |

} | |

} | |

} | |

} | |

//print mst | |

printMST(resultSet); | |

} | |

public void printMST(ResultSet[] resultSet){ | |

int total_min_weight = 0; | |

System.out.println("Minimum Spanning Tree: "); | |

for (int i = 1; i <vertices ; i++) { | |

System.out.println("Edge: " + i + " – " + resultSet[i].parent + | |

" key: " + resultSet[i].weight); | |

total_min_weight += resultSet[i].weight; | |

} | |

System.out.println("Total minimum key: " + total_min_weight); | |

} | |

} | |

public static void main(String[] args) { | |

int vertices = 6; | |

Graph graph = new Graph(vertices); | |

graph.addEdge(0, 1, 4); | |

graph.addEdge(0, 2, 3); | |

graph.addEdge(1, 2, 1); | |

graph.addEdge(1, 3, 2); | |

graph.addEdge(2, 3, 4); | |

graph.addEdge(3, 4, 2); | |

graph.addEdge(4, 5, 6); | |

graph.primMST(); | |

} | |

} |

**Output**:

Minimum Spanning Tree:

Edge: 1 - 2 key: 1 Edge: 2 - 0 key: 3 Edge: 3 - 1 key: 2 Edge: 4 - 3 key: 2 Edge: 5 - 4 key: 6 Total minimum key: 14