KOTLIN - PRIM'S ALGORITHM MINIMUM SPANNING TREE CODE

import java.util.*;

var vertices = LinkedList<String?>();
var adjcList = LinkedList<LinkedList<Edge>>() ;
var vertexVal = HashMap<String?,Int>();

// Stores the Minimum spanning Tree
var result = ArrayList<Edge>();

class Edge {

    var startVertex: String? = "";
    var endVertex: String? = "";
    var value = 0;
}


class MinHeap(vertexValue: HashMap<String?, Int>) {

    var vertexVal =  HashMap<String?, Int>();
    var verticesKeyArray: Array<String?> = emptyArray()

    init {

        vertexVal = vertexValue;
    }

    fun heapify(verticesArray: Array<String?>, root: Int, length: Int) {

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

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

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

            smallest = left;
        }

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

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

            heapify(verticesArray, smallest, length);
        }
    }

    fun buildHeap() {

        var verticesSet = vertexVal.keys;

        // Now convert the above keys to an Array.
        var verticesArray: Array<String?> = verticesSet.toTypedArray();

        var len = verticesArray.size-1;

        for (parent in (len-1)/ 2 downTo 0) {
            heapify(verticesArray, parent, len);
        }

        verticesKeyArray = verticesArray;

    }

    fun updateHeap(vertex: String?, length: Int) {

        vertexVal.put(vertex, length);

        // Get all the keys (i.e. Vertices ) for the Map.
        var verticesSet = vertexVal.keys;

        // Now convert the above keys to an Array.
        var verticesArray: Array<String?> = verticesSet.toTypedArray();

        var len = verticesArray.size-1;

        for (parent in (len-1)/ 2 downTo 0)
            heapify(verticesArray, parent, len);

        verticesKeyArray = verticesArray;
    }

    fun containsVertex(vertex: String?): Boolean{

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

    fun deleteMin(): String? {

        var temp = verticesKeyArray[0];

        var len = verticesKeyArray.size-1;

        verticesKeyArray[0] = verticesKeyArray[len];

        vertexVal.remove(temp);

        verticesKeyArray = Arrays.copyOf(verticesKeyArray, len);

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

        return temp;
    }

    fun getWeight(vertex: String? ): Int? {

        return vertexVal[vertex];
    }

    fun empty(): Boolean {

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

    }
}



class PrimMST {

    init {

        adjcList = LinkedList<LinkedList<Edge>>();
        vertices = LinkedList<String?>();
        vertexVal = LinkedHashMap<String?,Int>();

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

    fun primMST(){

        vertexVal = LinkedHashMap<String?,Int>();

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

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

        var minHeap = 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
            var 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.
            var spanningTreeEdge = vertexToEdge.get(currentVertex);
            if(spanningTreeEdge != null) {
                result.add(spanningTreeEdge);
            }

            // Get all the adjacent vertices and iterate through them.
            for(edge in getEdges(currentVertex)){

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

    fun getEdges(vertex: String?): List<Edge>{

        var edgeList = LinkedList<Edge>();

        var i = vertices.indexOf(vertex);

        var iter = adjcList.get(i).iterator();

        while (iter.hasNext()) {

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

        return edgeList;
    }

    fun constructAdjacencyList(vertex1: String, vertex2: String , edgeVal: Int) {

        var edge = Edge();

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

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

    fun insertVertex(vertex: String) {

        vertices.add(vertex);
    }



    fun printEdgeList() {

        for (edge in result) {

            println("The Edge between ${edge.startVertex} and ${edge.endVertex} is ${edge.value}" );
        }
    }
}

fun main(arr: Array<String>) {

    var primMST = 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();

}