Prim’s - Minimum Spanning Tree (MST) using Adjacency Matrix

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).
1. Get the vertex with the minimum key. Say its vertex u.
2. Include this vertex in MST and mark in mst[u] = true.
3. Iterate through all the adjacent vertices of above vertex u and update the keys if adjacent vertex is not already part of mst[].
We will use Result object to store the result of each vertex. Result object will store 2 information’s.
1. 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.
2. 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.
See the code for more understanding. Go through the commented description.

Time Complexity: O(|V|²).

Please see the animation below for better understanding.

1-13

2-13

3-13

4-13

5-15

6-13

7-13

8-13

9-13

10-13

11-13

12-13

13-13

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();
	}
	}

view raw

PrimAlgorithmAdjacencyMatrix.java

hosted with ❤ by GitHub

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

Prim’s – Minimum Spanning Tree (MST) |using Adjacency Matrix

Related Posts: