GO - PRIM'S ALGORITHM - MINIMUM SPANNING TREE - CODE

Example :

package main

import "fmt"
import "sort"
import "math"

var vertexVal map[string]int
var verticesKeyArray []string

var vertices []string
var adjcList [][]Edge
var vertexValPrim map[string]int

// Stores the Minimum spanning Tree
var result []Edge


type Edge struct {

    startVertex string
    endVertex string

    value int
}

func heapify(verticesArray []string, root int, length int) {

    left := (2*root)+1
    right := (2*root)+2
    smallest := root

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

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

        smallest = left
    }

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

        temp := verticesArray[root]
        verticesArray[root] = verticesArray[smallest]
        verticesArray[smallest] = temp

        heapify(verticesArray, smallest, length)
    }
}

func buildHeap() {

    var verticesArray []string
    
	for key := range vertexVal {
    	verticesArray = append(verticesArray, key)
	}

    len := len(verticesArray)-1

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

func updateHeap(vertex string, length int) {

    vertexVal[vertex] = length

    var verticesArray []string
    
	for key := range vertexVal {
    	verticesArray = append(verticesArray, key)
	}

    len := len(verticesArray)-1

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

func containsVertex(vertex string) bool{

	_, present := vertexVal[vertex]
    if (present) {
        return true
    } else {
        return false
    }
}    

func deleteMin() string{

    temp := verticesKeyArray[0]

    len := len(verticesKeyArray)-1

    verticesKeyArray[0] = verticesKeyArray[len]

    delete(vertexVal, temp)

	verticesKeyArray = append(verticesKeyArray[:len], verticesKeyArray[len+1:]...)

    if (len > 0) {
        heapify(verticesKeyArray, 0, len-1)
    }    

    return temp
}

func getWeight(vertex string) int {

        return vertexVal[vertex]
    }

func empty() bool {

    if (len(verticesKeyArray) > 0) {
        return false
    } else {
        return true
    }    

}



func primMST(){

    vertexValPrim = make(map[string]int)

    // Vertex to Edge Map
    vertexToEdge := make(map[string]Edge)

    // Assign all the initial values as infinity for all the Vertices.
    for _, v := range vertices {
        vertexValPrim[v] = math.MaxInt64
    }
    
    vertexVal = vertexValPrim

    // Call buildHeap() to create the MinHeap
    buildHeap()

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

    // Continue until the Min-Heap is not empty.
    for !empty() {
        // Extract minimum value vertex from Map in Heap
        currentVertex := 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.
        spanningTreeEdge := vertexToEdge[currentVertex]
        
        if(spanningTreeEdge != Edge{}) {
            result = append(result, spanningTreeEdge)
        }

        // Get all the adjacent vertices and iterate through them.
        for _, edge := range getEdges(currentVertex) {
            
            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(containsVertex(adjacentVertex) && getWeight(adjacentVertex) > edge.value) {
                
                // Replace the edge length with this edge weight.
                updateHeap(adjacentVertex, edge.value)
                    
                vertexToEdge[adjacentVertex] = edge
            }
        }
    }
}

func getEdges(vertex string) []Edge{

    var edgeList []Edge
    
    i := sort.StringSlice(vertices).Search(vertex)

    for j := 0; j < len(adjcList[i]); j++ {

        edgeList = append(edgeList, adjcList[i][j])
        }

    return edgeList
}

func constructTempList(tmpList *[]Edge, vertex1 string, vertex2 string, edgeVal int) {

    var edge Edge

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


	*tmpList = append(*tmpList, edge)
}

func constructAdjacencyList(adjcList *[][]Edge, tmpList *[]Edge) {

    *adjcList = append(*adjcList, *tmpList)
    *tmpList = nil
}

func insertVertex(vertex string) {

    vertices = append(vertices, vertex)
}

func printEdgeList() {

    for _, edge := range result {

        fmt.Println("The Edge between ",edge.startVertex," and ",edge.endVertex," is ",edge.value )
    }
}



	
func main() {
    
    var tempList[]Edge

    // Adding vertices one by one

    insertVertex("a")
    insertVertex("b")
    insertVertex("c")
    insertVertex("d")
    insertVertex("e")

	// Create Adjacency List with Edges.
	
	constructTempList(&tempList, "a", "b", 1)
    constructTempList(&tempList, "a", "c", 5)
    constructTempList(&tempList, "a", "d", 4)

	constructAdjacencyList(&adjcList, &tempList)

	constructTempList(&tempList, "b", "a", 1)
    constructTempList(&tempList, "b" ,"e", 8)

	constructAdjacencyList(&adjcList, &tempList)
    
	constructTempList(&tempList, "c", "a", 5)
    constructTempList(&tempList, "c", "d", 12)
    constructTempList(&tempList, "c", "e", 9)

	constructAdjacencyList(&adjcList, &tempList)

	constructTempList(&tempList, "d", "a", 4)
    constructTempList(&tempList, "d", "c", 12)
    constructTempList(&tempList, "d", "e", 3)

	constructAdjacencyList(&adjcList, &tempList)	

	constructTempList(&tempList, "e", "b", 8)
    constructTempList(&tempList, "e", "c", 9)
    constructTempList(&tempList, "e", "d", 3)

	constructAdjacencyList(&adjcList, &tempList)	

    primMST()

	printEdgeList()
}

Output :

1. First step is, we select any vertex and start from it(We have selected the vertex a in this case).


2. 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.


3. 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

LinkedList<String> vertices;

LinkedList<LinkedList<Edge>>  adjcList;

insertVertex("a")
insertVertex("b")
insertVertex("c")
insertVertex("d")
insertVertex("e")

// Create Adjacency List with Edges.
constructTempList(&tempList, "a", "b", 1)
constructTempList(&tempList, "a", "c", 5)
constructTempList(&tempList, "a", "d", 4)

constructAdjacencyList(&adjcList, &tempList)

constructTempList(&tempList, "b", "a", 1)
constructTempList(&tempList, "b" ,"e", 8)

constructAdjacencyList(&adjcList, &tempList)

constructTempList(&tempList, "c", "a", 5)
constructTempList(&tempList, "c", "d", 12)
constructTempList(&tempList, "c", "e", 9)

constructAdjacencyList(&adjcList, &tempList)

constructTempList(&tempList, "d", "a", 4)
constructTempList(&tempList, "d", "c", 12)
constructTempList(&tempList, "d", "e", 3)

constructAdjacencyList(&adjcList, &tempList)

constructTempList(&tempList, "e", "b", 8)
constructTempList(&tempList, "e", "c", 9)
constructTempList(&tempList, "e", "d", 3)

constructAdjacencyList(&adjcList, &tempList)

Click Here - For the creation process of Adjacency List.

Explanation of 'func constructTempList(tmpList *[]Edge, vertex1 string, vertex2 string, edgeVal int)'

func constructTempList(tmpList *[]Edge, vertex1 string, vertex2 string, edgeVal int) {

	var edge Edge

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

	*tmpList = append(*tmpList, edge)
}

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

constructTempList(&tempList, "a", "b", 1)

Now, if we look at the method definition,

func constructTempList(tmpList *[]Edge, vertex1 string, vertex2 string, edgeVal int)

vertex1 string is initialised with a.

vertex2 string is initialised with b.

edgeVal int is initialised with 1.

The next thing we do is, create an Edge type variable.

var edge Edge

And initialise the var edge Edge variable with the start vertex, end vertex and the length of the Edge.

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

And the Edge type variable looks somewhat like,

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

*tmpList = append(*tmpList, edge)

We repeat the same process for the other adjacent Edges. i.e.

And

constructTempList(&tempList, "a", "c", 5)
constructTempList(&tempList, "a", "d", 4)

Then we call the, constructAdjacencyList(&adjcList, &tempList).

Explanation of 'func constructAdjacencyList(adjcList *[][]Edge, tmpList *[]Edge)'

func constructAdjacencyList(adjcList *[][]Edge, tmpList *[]Edge) {

	*adjcList = append(*adjcList, *tmpList)
	*tmpList = nil
}

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

var adjcList [][]Edge

Now, we will be adding the adjacent edges to the first row of adjcList.

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

primMST.primMST();

Click Here - For Min-Heap Data Structure Recap.

There are four important method in the Min-Heap that are quite important.

They are :

1. func deleteMin() string


2. func updateHeap(vertex string, length int)


3. func buildHeap()


4. func heapify(verticesArray []string, root int, length int)

Now, if we look at the primMST() method,

We are creating a variable of map type,

vertexValPrim = make(map[string]int)

And initialising the var vertexVal map[string]int with vertexValPrim.

vertexVal = vertexValPrim

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

// Assign all the initial values as infinity for all the Vertices.
for _, v := range vertices {
	vertexValPrim[v] = math.MaxInt64
}

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 'func buildHeap()' method :

func buildHeap() {

	var verticesArray []string

	for key := range vertexVal {
		verticesArray = append(verticesArray, key)
	}

	len := len(verticesArray)-1

	for parent := int((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.

for key := range vertexVal {
	verticesArray = append(verticesArray, key)
}

Then, we take the length of the Array.

len := len(verticesArray)-1

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

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

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

Let us see.

Explanation of 'func heapify(verticesArray []string, root int, length int)' method :

func heapify(verticesArray []string, root int, length int) {

	left := (2*root)+1
	right := (2*root)+2
	smallest := root

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

		smallest = right

	} else if (left <= length) {

		smallest = left
	}

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

		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.

left := (2*root)+1
right := (2*root)+2
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[verticesArray[right]] < vertexVal[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[verticesArray[right]] < vertexVal[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[verticesArray[root]] > vertexVal[verticesArray[smallest]]) {

	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.
updateHeap("a",0)

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

Explanation of 'func updateHeap(vertex string, length int)' method :

func updateHeap(vertex string, length int) {

	vertexVal[vertex] = length

	var verticesArray []string

	for key := range vertexVal {
		verticesArray = append(verticesArray, key)
	}

	len := len(verticesArray)-1

	for parent := int((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[vertex] = length

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

for key := range vertexVal {
	verticesArray = append(verticesArray, key)
}

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.

Explanation of 'func primMST()' method :

func primMST(){

	vertexValPrim = make(map[string]int)

	// Vertex to Edge Map
	vertexToEdge := make(map[string]Edge)

	// Assign all the initial values as infinity for all the Vertices.
	for _, v := range vertices {
		vertexValPrim[v] = math.MaxInt64
	}

	vertexVal = vertexValPrim

	// Call buildHeap() to create the MinHeap
	buildHeap()

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

	// Continue until the Min-Heap is not empty.
	for !empty() {
		// Extract minimum value vertex from Map in Heap
		currentVertex := 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.
		spanningTreeEdge := vertexToEdge[currentVertex]

		if(spanningTreeEdge != Edge{}) {
			result = append(result, spanningTreeEdge)
		}

		// Get all the adjacent vertices and iterate through them.
		for _, edge := range getEdges(currentVertex) {

			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(containsVertex(adjacentVertex) && getWeight(adjacentVertex) > edge.value) {

				// Replace the edge length with this edge weight.
				updateHeap(adjacentVertex, edge.value)

				vertexToEdge[adjacentVertex] = edge
			}
		}
	}
}

• var vertexVal map[string]int
  
  The Map with key as vertex and value as the Edge length. We put this in the Heap.Also we will call var vertexVal map[string]int as Map in the Heap.


• vertexToEdge := make(map[string]Edge)
  
  The Map with key as vertex and value as the actual Edge.


• var result []Edge
  
  The Array that stores the final result. i.e. All the edges to be included in the Minimum Spanning Tree.

1. So, firstly we initialise the Map vertexValPrim. Which we are going to place in the Heap. Also, we will call the Map vertexVal as Map in the Heap.
   
   

   vertexValPrim = make(map[string]int)



2. Then we assign the Map vertexToEdge, where we will be storing the vertex as key and Edge as value.
   
   

   vertexToEdge := make(map[string]Edge)



3. The next task is to assign the value infinity to all the vertices in the Map vertexToEdge.
   
   

   for _, v := range vertices {
   	vertexValPrim[v] = math.MaxInt64
   }

   
   
   
   
   
   We can see the value math.MaxInt64 initialised to all the vertices. It can be said as infinity as it has a very large value that can be compared with infinity.


4. Then we initialise the Map vertexVal,
   
   

   var vertexVal map[string]int

   
   
   With the Map vertexValPrim, that we have created above.
   
   

   vertexVal = vertexValPrim



5. Next, we call the buildHeap(...) method of the Heap. That will create the Heap for us, by placing the elements in the right order.
   
   

   buildHeap();

   
   
   Just remember, in a Min-Heap the root element is always smaller than its left and right child.


6. Then we replace the value of the start element to 0 by calling the updateHeap(...) method.
   
   

   updateHeap("a",0);

   
   
   


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

   for !empty() {
   	// Extract minimum value vertex from Map in Heap
   	currentVertex := 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.
   	spanningTreeEdge := vertexToEdge[currentVertex]
   
   	if(spanningTreeEdge != Edge{}) {
   		result = append(result, spanningTreeEdge)
   	}
   	// Get all the adjacent vertices and iterate through them.
   	for _, edge := range getEdges(currentVertex) {
   
   		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(containsVertex(adjacentVertex) && getWeight(adjacentVertex) > edge.value) {
   
   			// Replace the edge length with this edge weight.
   			updateHeap(adjacentVertex, edge.value)
   
   			vertexToEdge[adjacentVertex] = edge
   		}
   	}
   }



8. Inside the for 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.
   
   

   currentVertex := deleteMin()

   
   
   Since, the vertex a has the smallest value i.e. 0. It is deleted from vertexVal. i.e. Heap in the Map.
   
   


9. 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 type variable, spanningTreeEdge gets null and is not added to the Mimimim Spanning Tree.
   
   

   spanningTreeEdge := vertexToEdge[currentVertex]
   if(spanningTreeEdge != Edge{}) {
   	result = append(result, spanningTreeEdge)
   }



10. 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 := range getEdges(currentVertex) {
    
    	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(containsVertex(adjacentVertex) && getWeight(adjacentVertex) > edge.value) {
    
    		// Replace the edge length with this edge weight.
    		updateHeap(adjacentVertex, edge.value)
    
    		vertexToEdge[adjacentVertex] = edge
    	}
    }



11. 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.
    
    

    adjacentVertex := edge.endVertex



12. 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(containsVertex(adjacentVertex) && getWeight(adjacentVertex) > edge.value) {
    
    	// Replace the edge length with this edge weight.
    	updateHeap(adjacentVertex, edge.value)
    
    	vertexToEdge[adjacentVertex] = edge
    }



13. 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.
    
    

    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[adjacentVertex] = edge

    
    
    

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