PRIM's ALGORITHM - MINIMUM SPANNING TREE CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

Example :

import java.util.*;

class Edge {

    String startVertex;
    String endVertex;

    int value;
}


class MinHeap {

    Map<String, Integer> vertexVal;
    String[] verticesKeyArray;

    MinHeap(Map<String, Integer> vertexVal){

        this.vertexVal = vertexVal;
    }

    public void heapify(String[] verticesArray,int root, int length) {

        int left = (2*root)+1;
        int right = (2*root)+2;
        int smallest = root;

        if (left < length && right <= length && vertexVal.get(verticesArray[right]) < vertexVal.get(verticesArray[left])) {

            smallest = right;
        }
        else if (left <= length){

            smallest = left;
        }

        if (vertexVal.get(verticesArray[root]) > vertexVal.get(verticesArray[smallest])) {

            String temp = verticesArray[root];
            verticesArray[root] = verticesArray[smallest];
            verticesArray[smallest] = temp;

            heapify(verticesArray, smallest, length);
        }
    }

    public void buildHeap() {

        Set<String> verticesSet = vertexVal.keySet();

        // Now convert the above keys to an Array.
        String[] verticesArray = new String[verticesSet.size()];
        verticesSet.toArray(verticesArray);

        int len = verticesArray.length-1;

        for (int parent = (len-1)/ 2; parent >= 0; parent--)
            heapify(verticesArray, parent, len);

        verticesKeyArray = verticesArray;

    }

    public void updateHeap(String vertex, int length) {

        vertexVal.put(vertex, length);

        // Get all the keys (i.e. Vertices ) for the Map.
        Set<String> verticesSet = vertexVal.keySet();

        // Now convert the above keys to an Array.
        String[] verticesArray = new String[verticesSet.size()];
        verticesSet.toArray(verticesArray);

        int len = verticesArray.length-1;

        for (int parent = (len-1)/ 2; parent >= 0; parent--)
            heapify(verticesArray, parent, len);

        verticesKeyArray = verticesArray;
    }

    boolean containsVertex(String vertex){

        if (vertexVal.containsKey(vertex))
            return true;
        else
            return false;
    }

    public String deleteMin() {

        String temp = verticesKeyArray[0];

        int len = verticesKeyArray.length-1;

        verticesKeyArray[0] = verticesKeyArray[len];

        vertexVal.remove(temp);

        verticesKeyArray = Arrays.copyOf(verticesKeyArray, len);

        if (len>0)
            heapify(verticesKeyArray, 0, len-1);

        return temp;
    }

    int getWeight(String vertex){

        return vertexVal.get(vertex);
    }

    public boolean empty() {

        if (verticesKeyArray.length>0)
            return false;
        else
            return true;

    }
}



public class PrimMST {

    LinkedList<String> vertices;
    LinkedList<LinkedList<Edge>>  adjcList;
    Map<String,Integer> vertexVal;

    // Stores the Minimum spanning Tree
    List<Edge> result;

    PrimMST(){

        adjcList = new LinkedList<>();
        vertices = new LinkedList<>();
        vertexVal = new LinkedHashMap<>();

        // Stores the Minimum spanning Tree
        result = new ArrayList<>();
    }

    public void primMST(){

        vertexVal = new LinkedHashMap<>();

        // Vertex to Edge Map
        Map<String, Edge> vertexToEdge = new HashMap<>();

        // Assign all the initial values as infinity for all the Vertices.
        for(String v : vertices) {
            vertexVal.put(v,Integer.MAX_VALUE);
        }

        MinHeap minHeap = new MinHeap(vertexVal);

        // Call buildHeap() to create the MinHeap
        minHeap.buildHeap();

        // Replace the value of start vertex to 0.
        minHeap.updateHeap("a",0);

        // Continue until the Min-Heap is not empty.
        while(!minHeap.empty()){
            // Extract minimum value vertex from Map in Heap
            String currentVertex = minHeap.deleteMin();

            // Need to get the edge for the vertex and add it to the Minimum Spanning Tree..
            // Just note, the edge for the source vertex will not be added.
            Edge spanningTreeEdge = vertexToEdge.get(currentVertex);
            if(spanningTreeEdge != null) {
                result.add(spanningTreeEdge);
            }

            // Get all the adjacent vertices and iterate through them.
            for(Edge edge : getEdges(currentVertex)){
            
                String adjacentVertex = edge.endVertex;
                
                // We check if adjacent vertex exist in 'Map in Heap' and length of the edge is with this vertex
                // is greater than this edge length.
                if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){
                
                    // Replace the edge length with this edge weight.
                    minHeap.updateHeap(adjacentVertex, edge.value);
                    
                    vertexToEdge.put(adjacentVertex, edge);
                }
            }
        }
    }

    List<Edge> getEdges(String vertex){

        List<Edge> edgeList = new LinkedList<>();

        int i = vertices.indexOf(vertex);

        for (Iterator iter = adjcList.get(i).iterator() ; iter.hasNext(); ) {

            edgeList.add((Edge) iter.next());
        }

        return edgeList;
    }

    void constructAdjacencyList(String vertex1, String vertex2, int edgeVal) {

        Edge edge = new Edge();

        edge.startVertex = vertex1;
        edge.endVertex = vertex2;
        edge.value = edgeVal;

        adjcList.add(new LinkedList<Edge>());
        adjcList.get(vertices.indexOf(vertex1)).add(edge);
    }

    void insertVertex(String vertex) {

        vertices.add(vertex);
    }



    void printEdgeList() {

        for (Edge edge : result) {

            System.out.println("The Edge between "+edge.startVertex+" and "+edge.endVertex+" is "+edge.value );
        }
    }

    public static void main(String[] args) {

        PrimMST primMST = new PrimMST();

        // Insert Vertices
        primMST.insertVertex("a");
        primMST.insertVertex("b");
        primMST.insertVertex("c");
        primMST.insertVertex("d");
        primMST.insertVertex("e");

        // Create Adjacency List with Edges.
        primMST.constructAdjacencyList("a", "b",1);
        primMST.constructAdjacencyList("a", "c",5);
        primMST.constructAdjacencyList("a", "d",4);

        primMST.constructAdjacencyList("b", "a",1);
        primMST.constructAdjacencyList("b" ,"e",8);

        primMST.constructAdjacencyList("c", "a",5);
        primMST.constructAdjacencyList("c", "d",12);
        primMST.constructAdjacencyList("c", "e",9);

        primMST.constructAdjacencyList("d", "a", 4);
        primMST.constructAdjacencyList("d", "c", 12);
        primMST.constructAdjacencyList("d", "e", 3);

        primMST.constructAdjacencyList("e", "b", 8);
        primMST.constructAdjacencyList("e", "c", 9);
        primMST.constructAdjacencyList("e", "d", 3);

        primMST.primMST();


        primMST.printEdgeList();
    }
}

Output :

The Edge between a and b is 1
The Edge between a and d is 4
The Edge between d and e is 3
The Edge between a and c is 5

Note : To understand, Prim's Algorithm for Minimum Spanning Tree. Prior knowledge of 'Heap' and 'Adjacency List' data structure is needed. But if you don't know, no worries. We will explain them in brief.

Let us recapitulate the 3 step process for Prim's Algorithm :

First step is, we select any vertex and start from it(We have selected the vertex 'a' in this case).
Then, we try finding the adjacent Edges of that Vertex(In this case, we try finding the adjacent edges of vertex 'a').

This is where, we will be using 'Adjacency List' for finding the Adjacent Edges.
Next, we will take all the Adjacent edges from above and check, which edge has the smallest length/weight.

Again, this is where, we will be using 'Min-Heap' for finding the Adjacent Edges.

Code explanation for Prim's Algorithm - Minimum Spanning Tree

Let us take the below graph, to understand the above code.

The first task is to construct the Graph. So, we need to store the Vertices first.

LinkedList<String> vertices;

And also we know, we have to represent the edges as 'Adjacency List'.

LinkedList<LinkedList<Edge>>  adjcList;

Eventually, in the 'main(...)' method. We have initialised the vertices,

 
primMST.insertVertex("a");
primMST.insertVertex("b");
primMST.insertVertex("c");
primMST.insertVertex("d");
primMST.insertVertex("e");

And, created the 'Adjacency List' with Edges.

 
// Create Adjacency List with Edges.
primMST.constructAdjacencyList("a", "b", 1);
primMST.constructAdjacencyList("a", "c", 5);
primMST.constructAdjacencyList("a", "d", 4);

primMST.constructAdjacencyList("b", "a", 1);
primMST.constructAdjacencyList("b" ,"e", 8);

primMST.constructAdjacencyList("c", "a", 5);
primMST.constructAdjacencyList("c", "d", 12);
primMST.constructAdjacencyList("c", "e", 9);

primMST.constructAdjacencyList("d", "a", 4);
primMST.constructAdjacencyList("d", "c", 12);
primMST.constructAdjacencyList("d", "e", 3);

primMST.constructAdjacencyList("e", "b", 8);
primMST.constructAdjacencyList("e", "c", 9);
primMST.constructAdjacencyList("e", "d", 3);

Let us understand creation process of Adjacency List. If you already know it, you can skip.

Click Here - For the creation process of Adjacency List.

Code explanation for Prim's Algorithm - Minimum Spanning Tree

void constructAdjacencyList(String vertex1, String vertex2, int edgeVal) {

    Edge edge = new Edge();

    edge.startVertex = vertex1;
    edge.endVertex = vertex2;
    edge.value = edgeVal;

    adjcList.add(new LinkedList<Edge>());
    adjcList.get(vertices.indexOf(vertex1)).add(edge);
}

void insertVertex(String vertex) {

    vertices.add(vertex);
}

Let us take the example of the Edge (a,b) with length 1 and understand the above code.

primMST.constructAdjacencyList("a", "b", 1);

Now, if we look at the method definition,

void constructAdjacencyList(String vertex1, String vertex2, int edgeVal)
	
'String vertex1' is initialised with 'a'.
'String vertex2' is initialised with 'b'.
'int edgeVal' is initialised with '1'.

The next thing we do is, create an 'Edge' object.

Edge edge = new Edge();

And initialise the 'Edge edge' object with the start vertex, end vertex and the length of the Edge.

edge.startVertex = vertex1;
edge.endVertex = vertex2;
edge.value = edgeVal;

And the Edge object looks somewhat like,

Now, since we have the Edge (a,b) initialised. The next task would be, to add this Edge to the AdjacencyList.

And as we have seen, there is a 2D LinkedList to store the Adjacency List.

LinkedList<LinkedList<Edge>> adjcList;

Now, we will be creating the first row of LinkedList,

adjcList.add(new LinkedList<Edge>());

And then we will try finding out, for which vertex we are going to insert the Edge.

adjcList.get(vertices.indexOf(vertex1)).add(edge);

In simple words, 'vertices.indexOf(vertex1)' will tell us about the position of the start vertex.

In this case, the start vertex is 'a'. And 'vertices.indexOf(vertex1)' will tell us about its position, i.e. 0.

So, if we substitute the line,

adjcList.get(vertices.indexOf(vertex1)).add(edge);

With the value of 'vertices.indexOf(vertex1)',

adjcList.get(0).add(edge);

The 'edge' would be added to the 0th location of the 2d LinkedList.

This is how a 2D LinkedList looks like. Just remember, the empty blocks are not yet created, but will be created eventually.

For now, only the first row is created with the first column where the edge

is inserted.

Next, when we try to insert the second adjacent edge of a i.e. a,c.

 primMST.constructAdjacencyList("a", "c", 5);

An edge object will be created

edge.startVertex = vertex1;
edge.endVertex = vertex2;
edge.value = edgeVal;

And the Edge object looks somewhat like,

Once again the start vertex is 'a'. And 'vertices.indexOf(vertex1)' will tell us about its position, i.e. 0.

So, if we substitute the line,

adjcList.get(vertices.indexOf(vertex1)).add(edge);

With the value of 'vertices.indexOf(vertex1)',

adjcList.get(0).add(edge);

The 'edge' would be added to the 1st row of the 2d LinkedList, just next to the first edge.

Similarly, we insert the third adjacent edge of 'a' i.e. a,d.

 primMST.constructAdjacencyList("a", "d", 4);

An edge object will be created

edge.startVertex = vertex1;
edge.endVertex = vertex2;
edge.value = edgeVal;

And the Edge object looks somewhat like,

Once again the start vertex is 'a'. And 'vertices.indexOf(vertex1)' will tell us about its position, i.e. 0.

So, if we substitute the line,

adjcList.get(vertices.indexOf(vertex1)).add(edge);

With the value of 'vertices.indexOf(vertex1)',

adjcList.get(0).add(edge);

The 'edge' would be added to the 1st row of the 2d LinkedList, just next to the first edge.

Similarly, we insert the adjacent edge of 'b' i.e. b,a.

primMST.constructAdjacencyList("b", "a", 1);

An edge object will be created

edge.startVertex = vertex1;
edge.endVertex = vertex2;
edge.value = edgeVal;

And the Edge object looks somewhat like,

Now, the start vertex is 'b'. And 'vertices.indexOf(vertex1)' will tell us about its position, i.e. 1.

So, if we substitute the line,

adjcList.get(vertices.indexOf(vertex1)).add(edge);

With the value of 'vertices.indexOf(vertex1)',

adjcList.get(1).add(edge);

And this time, the 'edge' would be added to the 2nd row of the 2d LinkedList.

And eventually the AdjacencyList with Edges would be created with the 2D LinkedList.

Once we are done creating the AdjacencyList with Edges. The next task would be to call the actual method for Prim's Algorithm,

primMST.primMST();

Before we understand 'primMST()' method in detail. Let us understand the Min-Heap Data Structure.

If you already know Min-Heap Data Structure, you can skip the below part.

Click Here - For Min-Heap Data Structure Recap.

There are four important method in the MinHeap class that are quite important.

They are :

public String deleteMin()
public void updateHeap(String vertex, int length)
public void buildHeap()
public void heapify(String[] verticesArray,int root, int length)

Now, if we look at the 'primMST()' method, we could see that initially the MinHeap object is created using a parameterised constructor.

MinHeap minHeap = new MinHeap(vertexVal);

And if we look at the Constructor definition,

MinHeap(Map<String, Integer> vertexVal){

    this.vertexVal = vertexVal;
}

The Map 'Map<String, Integer> vertexVal' is getting initialised here.

this.vertexVal = vertexVal;

Where, 'this.vertexVal' is the class attribute,

Map<String, Integer> vertexVal;

Next, we initialise the Map with the vertices as key and assign the value as Integer.MAX_VALUE. This 'Integer.MAX_VALUE' is so large that it could be compared with infinity.

// Assign all the initial values as infinity for all the Vertices.
for(String v : vertices) {
    vertexVal.put(v,Integer.MAX_VALUE);
}

So, the Map 'vertexVal' is loaded with values.

Next, we call the 'buildHeap()' method to create the MinHeap, with the values of the Map 'vertexVal'.

 minHeap.buildHeap();

Explanation of 'void buildHeap()' method :

public void buildHeap() {

    Set<String> verticesSet = vertexVal.keySet();

    // Now convert the above keys to an Array.
    String[] verticesArray = new String[verticesSet.size()];
    verticesSet.toArray(verticesArray);

    int len = verticesArray.length-1;

    for (int parent = (len-1)/ 2; parent >= 0; parent--)
        heapify(verticesArray, parent, len);

    verticesKeyArray = verticesArray;

}

Just remember, Map is not a good Data Structure for Heap. Whereas array is an excellent Data Structure for Heap.

So, we take the keys from the Map and create an Array out of it.

To do this, there is a two step process involved.

First, we extract the key from the Map and put it into a Set.

Set<String> verticesSet = vertexVal.keySet();

Second, we create an Array and convert the Set to the Array.

String[] verticesArray = new String[verticesSet.size()];
    
verticesSet.toArray(verticesArray);

Then, we take the length of the Array.

int len = verticesArray.length-1;

Then, we divide the Array into two parts and run a 'for' loop. Then call the Heapify method.

for (int parent = (len-1)/ 2; parent >= 0; parent--)
        heapify(verticesArray, parent, len);

So, what does the heapify(..) method do?

Let us see.

Explanation of 'void heapify(String[] verticesArray,int root, int length)' method :

public void heapify(String[] verticesArray,int root, int length) {

    int left = (2*root)+1;
    int right = (2*root)+2;
    int smallest = root;

    if (left < length && right <= length && vertexVal.get(verticesArray[right]) < vertexVal.get(verticesArray[left])) {

        smallest = right;
    }
    else if (left <= length){

        smallest = left;
    }

    if (vertexVal.get(verticesArray[root]) > vertexVal.get(verticesArray[smallest])) {

        String temp = verticesArray[root];
        verticesArray[root] = verticesArray[smallest];
        verticesArray[smallest] = temp;

        heapify(verticesArray, smallest, length);
    }
}

Since, all the values of the Map 'vertexVal' are infinity now. So, it doesn't matter how the values will be inserted in the Min-Heap.

For the sake of understanding, let us understand the functionality of 'heapify(...)' method.

So, we have passed the 'verticesArray', 'root' element and the 'length' of the Array to 'heapify(...)' method.

Then, we have calculated the left, right and root element of the Heap.

int left = (2*root)+1;
int right = (2*root)+2;
int smallest = root;

Since, this is a Min-Heap. The smallest element would be at the root of the Heap.

So, we try initialising the 'smallest' element with its right value.

And the below 'if' condition checks, if the 'left' and 'right' element is less than the length of the Array.

if (left < length && right <= length && vertexVal.get(verticesArray[right]) < vertexVal.get(verticesArray[left])) {

    smallest = right;
}
else if (left <= length){

    smallest = left;
}

And, if the element on the right side of the Map 'vertexVal' is less than the element on the right side.

vertexVal.get(verticesArray[right]) < vertexVal.get(verticesArray[left])

Then element on the right side of the Map is the smallest element.

smallest = right;

And in the else part, we can assume that the element on the left side of the Map has the smallest element.

smallest = left;

Now, since we got the smallest element. We need to check if the actual 'root' element is greater than the 'smallest' element or not.

if (vertexVal.get(verticesArray[root]) > vertexVal.get(verticesArray[smallest])) {

    String temp = verticesArray[root];
    verticesArray[root] = verticesArray[smallest];
    verticesArray[smallest] = temp;

    heapify(verticesArray, smallest, length);
}

And this is where, we swap the contents of the 'root' element and the 'smallest' element. Assuming the element in the root is greater than the smallest element.

Which shouldn't be. As the root element should always be the smallest element.

Then a recursive call is made to heapify(...) method.

heapify(verticesArray, smallest, length);

And the recursion continues until all the elements are arranged in MinHeap.

In the next line, we would update the value of source element 'a' to 0.

 
// Replace the value of start vertex to 0.
minHeap.updateHeap("a",0);

Now, if we see the updateHeap(...) method,

Explanation of 'void updateHeap(String vertex, int length)' method :

public void updateHeap(String vertex, int length) {

    vertexVal.put(vertex, length);

    // Get all the keys (i.e. Vertices ) for the Map.
    Set<String> verticesSet = vertexVal.keySet();

    // Now convert the above keys to an Array.
    String[] verticesArray = new String[verticesSet.size()];
    verticesSet.toArray(verticesArray);

    int len = verticesArray.length-1;

    for (int parent = (len-1)/ 2; parent >= 0; parent--)
        heapify(verticesArray, parent, len);

    verticesKeyArray = verticesArray;
}

The first thing we do is, replace the value in the Map 'vertexVal'.

 
vertexVal.put(vertex, length);

Then we follow the same process we followed above. i.e. Extract the keys from the Map. Make it a Set and then convert the Set into an Array.

 
Set<String> verticesSet = vertexVal.keySet();

String[] verticesArray = new String[verticesSet.size()];
    
verticesSet.toArray(verticesArray);

Then we call the heapify(...) method. Because we have updated a new value and in that case the Heap has to be rearranged to form a Min-Heap.

Now, that we have understood Min-Heap. Let us understand the details about the actual method that calculates the Minimum Spanning Tree using Prim's Algorithm.

public void primMST(){

    vertexVal = new LinkedHashMap<>();

    // Vertex to Edge Map
    Map<String, Edge> vertexToEdge = new HashMap<>();

    // Assign all the initial values as infinity for all the Vertices.
    for(String v : vertices) {
        vertexVal.put(v,Integer.MAX_VALUE);
    }

    MinHeap minHeap = new MinHeap(vertexVal);

    // Call buildHeap() to create the MinHeap
    minHeap.buildHeap();

    // Replace the value of start vertex to 0.
    minHeap.updateHeap("a",0);

    // Continue until the Min-Heap is not empty.
    while(!minHeap.empty()){
        // Extract minimum value vertex from Map in Heap
            String currentVertex = minHeap.deleteMin();

        // Need to get the edge for the vertex and add it to the Minimum Spanning Tree..
        // Just note, the edge for the source vertex will not be added.
        Edge spanningTreeEdge = vertexToEdge.get(currentVertex);
        if(spanningTreeEdge != null) {
            result.add(spanningTreeEdge);
        }

        // Get all the adjacent vertices and iterate through them.
        for(Edge edge : getEdges(currentVertex)){
            
            String adjacentVertex = edge.endVertex;
                
            // We check if adjacent vertex exist in 'Map in Heap' and length of the edge is with this vertex
            // is greater than this edge length.
            if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){
                
                // Replace the edge length with this edge weight.
                minHeap.updateHeap(adjacentVertex, edge.value);
                    
                vertexToEdge.put(adjacentVertex, edge);
            }
        }
    }
}

Three things to remember :

```
 Map<String,Integer> vertexVal;
```
The Map with key as vertex and value as the Edge length. We put this in the Heap.Also we will call 'Map<String,Integer> vertexVal' as 'Map in the Heap'.
```
Map<String, Edge> vertexToEdge;
```
The Map with key as vertex and value as the actual Edge.
```
List<Edge> result;
```
The List that stores the final result. i.e. All the edges to be included in the Minimum Spanning Tree.

Now, let us look at the steps involved :

So, firstly we initialise the Map 'vertexVal'. Which we are going to place in the Heap. Also, we will call the Map 'vertexVal' as 'Map in the Heap'.
```
vertexVal = new LinkedHashMap<>();
```
Then we assign the Map 'vertexToEdge', where we will be storing the vertex as key and Edge as value.
```
Map<String, Edge> vertexToEdge = new HashMap<>();
```
The next task is to assign the value infinity to all the vertices in the Map 'vertexToEdge'.
```
for(String v : vertices) {
    vertexVal.put(v,Integer.MAX_VALUE);
}
```
We can see the value 'Integer.MAX_VALUE' initialised to all the vertices. It can be said as infinity as it has a very large value that can be compared with infinity.

Then we initialise MinHeap by passing the Map as a parameter to it constructor.
```
MinHeap minHeap = new MinHeap(vertexVal);
```

Next, we call the buildHeap(...) method of the Heap. That will create the Heap for us,by placing the elements in the right order.
```
minHeap.buildHeap();
```
Just remember, in a Min-Heap the root element is always smaller than its left and right child.

Then we replace the value of the start element to 0 by calling the 'updateHeap(...)' method.
```
minHeap.buildHeap();
```
minHeap.updateHeap("a",0);

Then we come to the 'while' loop, that continues until the Min-Heap is empty.

while(!minHeap.empty()){
    // Extract minimum value vertex from Map in Heap
    String currentVertex = minHeap.deleteMin();

    // Need to get the edge for the vertex and add it to the Minimum Spanning Tree.
    // Just note, the edge for the source vertex will not be added.
    Edge spanningTreeEdge = vertexToEdge.get(currentVertex);
    if(spanningTreeEdge != null) {
        result.add(spanningTreeEdge);
    }

    // Get all the adjacent vertices and iterate through them.
    for(Edge edge : getEdges(currentVertex)){
            
        String adjacentVertex = edge.endVertex;
                
        // We check if adjacent vertex exist in 'Map in Heap' and length of the edge is with this vertex
        // is greater than this edge length.
        if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){
                
            // Replace the edge length with this edge weight.
            minHeap.updateHeap(adjacentVertex, edge.value);
                    
            vertexToEdge.put(adjacentVertex, edge);
        }
    }
}

Inside the 'while' loop, the first thing we do is, get the smallest element from the Heap. That is the root element.

Also we delete the root element from the Heap at the same time.

And the deleteMin() method of the Heap does the work for us.
```
String currentVertex = minHeap.deleteMin();
```
Since, the vertex 'a' has the smallest value i.e. 0. It is deleted from 'vertexVal'. i.e. 'Heap in the Map'.
Then we go to the Map 'vertexToEdge' which has the key as vertex and the value as actual Edge. And try getting the Edge for that corresponding vertex (i.e. 'a').

But in this case, the Map 'vertexToEdge' has not yet being initialised.

Why is it so?

Because 'a' is the starting vertex and we won't be adding the starting vertex to the Minimum Spanning Tree.

So, the 'Edge spanningTreeEdge' gets null and is not added to the Mimimim Spanning Tree.
```
Edge spanningTreeEdge = vertexToEdge.get(currentVertex);
if(spanningTreeEdge != null) {
    result.add(spanningTreeEdge);
}
```

The next task we have done is getting the adjacent vertices and iterate through and get the corresponding Edges for the vertices.

And the getEdges() method helps us getting the Adjacent Edges of the vertex 'a'.

for(Edge edge : getEdges(currentVertex)){
            
    String adjacentVertex = edge.endVertex;
                
    // We check if adjacent vertex exist in 'Map in Heap' and length of the edge associated with this vertex
    // is greater than this edge length.
    if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){
                
        // Replace the edge length with this edge weight.
        minHeap.updateHeap(adjacentVertex, edge.value);
                    
        vertexToEdge.put(adjacentVertex, edge);
    }
}

Once we have the first Adjacent Edge i.e. 'a,b',

We would only take the end vertex from it. And 'edge' object already has the 'endVertex'.
```
String adjacentVertex = edge.endVertex;
```
Now, that we got the 'adjacentVertex' i.e. 'b'. The next thing we check is, if this 'adjacentVertex' i.e. 'b', exist in 'Map in Heap' and also check, if the value of the edge length associated with this vertex i.e. The value associated with vertex 'b' is greater than this edge length i.e. The length of edge a,b. Which is 1.

So, we find that vertex 'b' is present in 'vertexVal' i.e. 'Map in heap'.

And the value of 'b' in 'vertexVal' i.e. 'Map in heap' is ∞. Which is greater that the value of the edge i.e. 1.

So, the 'if' condition is satisfied and we get into the 'if' block.
```
if(minHeap.containsVertex(adjacentVertex) && minHeap.getWeight(adjacentVertex) > edge.value){
                
    minHeap.updateHeap(adjacentVertex, edge.value);
                    
    vertexToEdge.put(adjacentVertex, edge);
}
```
Now, since we are in the blocks of 'if' statement, we had updated the vertex with the new value of the Edge i.e. 1.
```
minHeap.updateHeap(adjacentVertex, edge.value);
```
Similarly, we put the actual edge i.e. a,b to the value of vertex 'b' in the Map 'vertexToEdge' that stores vertex as key and the Edge associated to it as value.
```
vertexToEdge.put(adjacentVertex, edge);
```
The similar process gets repeated and we get the Minimum Spanning Tree using Prim's Algorithm.

Note : Have you noticed the link between the Map 'vertexToEdge' and 'vertexVal'(i.e. Map in Heap)? The Edge length is stored in the Map 'vertexVal'(i.e. Map in Heap) and the actual Edge associated to it is stored in the Map 'vertexToEdge'.

Say vertex 'b' has the Edge length 1 that is stored in the Map 'vertexVal'(i.e. Map in Heap) and the actual Edge a,b is stored in the Map 'vertexToEdge'.

Time Complexity of Prim's Algorithm for Minimum Spanning Tree

The time complexity of Prim's Algorithm for Minimum Spanning Tree is : O(E logV)

Where E is the Edge
And V is the Vertex

The time complexity O(E logV) is only when we will be using the above combination of MIn-Heap and Adjacency List.

❮❮ PREV NEXT ❯❯