Earlier we have seen the implementation of prim’s algorithm using priority queue with decrease key and how decrease key has increased the time complexity. In this article we will improve the implementation(without decrease key) and reduce the complexity from **O(EVlogV) **to **O(ElogV)**.

If you are reading prim’s algorithm for the first time then we recommend reading the following articles before continuing

**Example**:

**Why one more implementation: **

First we saw implementation using adjacency matrix which was easy to implement but complexity was O(V^{2}), then we discussed implementation using adjacency list with priority queue but complexity got worst O(EVlogV). After that we discussed adjacency list with min-Heap and we got the best results with time complexity O(ElogV) but we implemented own min-heap with made the implantation but complex. In this article will achieve same time complexity O(ElogV) using priority queue.

**How our earlier implementation using priority queue was not efficient**–

In our earlier implementation of prim’s algorithm using priority queue with decrease key function, the time complexity was on the higher side because of decrease key function. Since there is no easy way to implement the decrease key in priority queue we followed the expensive approach. In this article we will implement it without using decrease key.

Let’s first see the decrease key algorithm for priority queue.

- Iterate through all the nodes in priority queue.
- Find the node for which we want to decrease the key.
- Once find the node, remove it from the priority queue update it and add it again.

**Improvements: **

- Do not insert all the vertices in the beginning.
- Insert only vertices which are not in MST and has been visited through one of the vertex.
- Use Pair Class and use pair object as a priority queue node. (Please read about Pair class)

**Complete Algorithm**:

- Create priority queue of size = no of vertices.
- Will create pair object for each vertex with two information’s, vertex and key. (similar to heap node)
- Override the Comparator of priority queue to sort them based on the key
- Use mst[] to keep track of the vertices which are currently in MST.
- Create key[] to keep track of key value for each vertex. , initialize all keys as MAX_VAL for the first vertex for which key will 0. (Start from first vertex).
- Create a pair object for vertex 0 with key 0 and insert into priority queue.
- while priority queue is not empty
- Extract the min node from the priority queue, say it vertex
and add it to the MST, mst[*u*] = true.*u* - Iterate through all the adjacent vertices of above vertex
and if adjacent vertex(say it’s*u*) and if*v*is not in MST and key of vertex*v*>*v*weight then create a pair object with vertex*u-v*and key =*v*weight and insert it into priority queue.*u-v* - Update the key[
] =*v**u-v*

- Extract the min node from the priority queue, say it vertex
- We will use Result object to store the result of each vertex. Result object will store two 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 animation below for more understanding.

**Time Complexity:**

Total vertices: V, Total Edges : E

- O(logV) – to extract each vertex from queue. So for V vertices – O(VlogV)
- O(logV) – each time new pair object with new key value of a vertex and will be done for at most once for each edge. So for total E edge – O(ElogV)
- So over all complexity: O(VlogV) + O(ElogV) = O((E+V)logV) =
**O(ElogV)**

**Complete Code**: <

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import javafx.util.Pair; | |

import java.util.Comparator; | |

import java.util.LinkedList; | |

import java.util.PriorityQueue; | |

public class PrimAlgorithmPQBetter { | |

static class Edge { | |

int source; | |

int destination; | |

int weight; | |

public Edge(int source, int destination, int weight) { | |

this.source = source; | |

this.destination = destination; | |

this.weight = weight; | |

} | |

} | |

static class ResultSet { | |

int parent; | |

int weight; | |

} | |

static class Graph { | |

int vertices; | |

LinkedList<Edge>[] adjacencylist; | |

Graph(int vertices) { | |

this.vertices = vertices; | |

adjacencylist = new LinkedList[vertices]; | |

//initialize adjacency lists for all the vertices | |

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

adjacencylist[i] = new LinkedList<>(); | |

} | |

} | |

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

Edge edge = new Edge(source, destination, weight); | |

adjacencylist[source].addFirst(edge); | |

edge = new Edge(destination, source, weight); | |

adjacencylist[destination].addFirst(edge); //for undirected graph | |

} | |

public void primMST(){ | |

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

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

int [] key = new int[vertices]; //keys used to store the key to know whether priority queue update is required | |

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

} | |

//Initialize priority queue | |

//override the comparator to do the sorting based keys | |

PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(vertices, new Comparator<Pair<Integer, Integer>>() { | |

@Override | |

public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) { | |

//sort using key values | |

int key1 = p1.getKey(); | |

int key2 = p2.getKey(); | |

return key1–key2; | |

} | |

}); | |

//create the pair for for the first index, 0 key 0 index | |

key[0] = 0; | |

Pair<Integer, Integer> p0 = new Pair<>(key[0],0); | |

//add it to pq | |

pq.offer(p0); | |

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

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

//while priority queue is not empty | |

while(!pq.isEmpty()){ | |

//extract the min | |

Pair<Integer, Integer> extractedPair = pq.poll(); | |

//extracted vertex | |

int extractedVertex = extractedPair.getValue(); | |

mst[extractedVertex] = true; | |

//iterate through all the adjacent vertices and update the keys | |

LinkedList<Edge> list = adjacencylist[extractedVertex]; | |

for (int i = 0; i <list.size() ; i++) { | |

Edge edge = list.get(i); | |

//only if edge destination is not present in mst | |

if(mst[edge.destination]==false) { | |

int destination = edge.destination; | |

int newKey = edge.weight; | |

//check if updated key < existing key, if yes, update if | |

if(key[destination]>newKey) { | |

//add it to the priority queue | |

Pair<Integer, Integer> p = new Pair<>(newKey, destination); | |

pq.offer(p); | |

//update the resultSet for destination vertex | |

resultSet[destination].parent = extractedVertex; | |

resultSet[destination].weight = newKey; | |

//update the key[] | |

key[destination] = newKey; | |

} | |

} | |

} | |

} | |

//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.addEgde(0, 1, 4); | |

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

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

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

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

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

graph.addEgde(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