# Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue with decrease key

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

We strongly recommend to read – prim’s algorithm and implementation of priority queue.

Example: Implementation – Adjacency List and Priority Queue with decrease key

In last article we discussed the implementation using min-heap. In this article our approach will be same except in place of min-heap we will use priority queue with decrease-key function. This approach will have more time complexity which we will improve in the next article – priority queue – better approach.

1. Create priority queue of size = no of vertices.
2. Create a heapNode for each vertex which will store two information’s.
1. Vertex
2. key
3. Use inPriorityQueue[] to keep track of the vertices which are currently in priority queue.
4. Create key[] to keep track of key value for each vertex. (keep updating it as heapNode key for each vertex)
5. For each heapNode, initialize key as MAX_VAL except the heapNode for the first vertex for which key will 0. (Start from first vertex).
6. Override the Comparator of priority queue to sort them based on the key. Insert all the heapNodes into priority queue. inPriorityQueue [v] = true for all vertices.
7. while priority queue is not empty
1. Extract the min node from the priority queue, say it vertex u and add it to the MST.
2. Decrease key: Iterate through all the adjacent vertices of above vertex u and if adjacent vertex(say it’s v) is still part of inPriorityQueue [] (means not in MST) and key of vertex v> u-v weight then update the node in priority queue. Find the node for vertex v in priority queue, remove it, and update it as key of vertex v = u-v weight and insert it again. This step increases the complexity of this implementation.
8. 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.

Time Complexity:

Total vertices: V, Total Edges : E

• O(logV) – to extract each vertex from queue. So for V vertices – O(VlogV)
• O(V) – each time decrease the key value of a vertex. Decrease key will be called for at most once for each edge. So for total E edge – O(EV)
• So over all complexity: O(VlogV) + O(EVlogV) = O(EVlogV)

See the animation below for more understanding               PQ 1-15
PQ 2-15
PQ 3-15
PQ 4-15
PQ 5-15
PQ 6-15
PQ 7-15
PQ 8-15
PQ 9-15
PQ 10-15
PQ 11-15
PQ 12-15
PQ 13-15
PQ 14-15
PQ 15-15    Complete Code:

 import java.util.*; public class PrimsPQ { 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 HeapNode{ int vertex; int key; } static class ResultSet { int parent; int weight; } static class Graph { int vertices; LinkedList[] adjacencylist; Graph(int vertices) { this.vertices = vertices; adjacencylist = new LinkedList[vertices]; //initialize adjacency lists for all the vertices for (int i = 0; i (); } } 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[] inPriorityQueue = 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 // //create heapNode for all the vertices HeapNode [] heapNodes = new HeapNode[vertices]; for (int i = 0; i pq = new PriorityQueue<>(vertices, new Comparator() { @Override public int compare(HeapNode o1, HeapNode o2) { return o1.key –o2.key; } }); //add all the vertices to priority queue for (int i = 0; i list = adjacencylist[extractedVertex]; for (int i = 0; i newKey) { decreaseKey(pq, newKey, destination); //update the parent node for destination resultSet[destination].parent = extractedVertex; resultSet[destination].weight = newKey; key[destination] = newKey; } } } } //print mst printMST(resultSet); } public void decreaseKey(PriorityQueue pq, int newKey, int vertex){ //iterate through nodes in priority queue and update the key for the vertex Iterator it = pq.iterator(); while (it.hasNext()) { HeapNode heapNode = (HeapNode) it.next(); if(heapNode.vertex==vertex) { pq.remove(heapNode); heapNode.key = newKey; pq.offer(heapNode); break; } } } public void printMST(ResultSet[] resultSet){ int total_min_weight = 0; System.out.println("Minimum Spanning Tree: "); for (int i = 1; i

view raw
PrimsPQ.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
```