Skip to main content

Prim's algorithm using adjacency list

Prim's is an greedy algorithm, which are used to find a minimum spanning tree of a weighted undirected graph. Let us understand the used terminology of prim's algorithm.

What is graph? : A graph is a collection of nodes called vertices, and a link that connects two nodes is called an edge of the graph. For example.

Graph example

The edge of graph are provide a path between two nodes. Using of edges is decided the type of graph. For example.

What is Undirected graph? : Undirected graph each link is connected to two nodes. And in this graph link are not have any direction means using of this edges are traversed in both direction.

What is Weighted of edge? : Weighted graph is assigned a number to each edge which represents distance or weight to an edge. its also known as edge-weighted graph. The weight of the edge can be positive negative. It depend upon situation.

What is cycle in graph? : Cycle graph or circular graph is collection of vertex and edges which create a loop.

What is Minimum spanning Tree? : Minimum spanning tree is subset of graph, Which is covered all vertices with minimum number of edges without create any cycles.

Minimum spanning tree example

What is prim's algorithm ? : Prim's algorithm is an greedy algorithm, Which are used to find minimum spanning tree.

Given below mention solution of this problem using adjacency list..

import java.util.ArrayList;
/*
    Java program for
    Prim's algorithm using adjacency list
*/
class Edge
{
    // Source node
    int u;
    // Destination node
    int v;
    // Edge weight
    int weight;
    public Edge(int u, int v, int weight)
    {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }
}
class HeapNode
{
    int vertex;
    int key;
}
class ResultSet
{
    int parent;
    int weight;
}
class MinHeap
{
    int capacity;
    int currentSize;
    HeapNode[] node;
    int[] indexes;
    public MinHeap(int capacity)
    {
        this.capacity = capacity;
        node = new HeapNode[capacity + 1];
        indexes = new int[capacity];
        node[0] = new HeapNode();
        node[0].key = Integer.MIN_VALUE;
        node[0].vertex = -1;
        currentSize = 0;
    }
    public void swap(int a, int b)
    {
        HeapNode temp = node[a];
        node[a] = node[b];
        node[b] = temp;
    }
    public boolean isEmpty()
    {
        return currentSize == 0;
    }
    public int heapSize()
    {
        return currentSize;
    }
    public void bubbleUp(int pos)
    {
        int parentIdx = pos / 2;
        int currentIdx = pos;
        while (currentIdx > 0 
               && node[parentIdx].key > node[currentIdx].key)
        {
            HeapNode currentNode = node[currentIdx];
            HeapNode parentNode = node[parentIdx];
            indexes[currentNode.vertex] = parentIdx;
            indexes[parentNode.vertex] = currentIdx;
            swap(currentIdx, parentIdx);
            currentIdx = parentIdx;
            parentIdx = parentIdx / 2;
        }
    }
    public void insert(HeapNode x)
    {
        currentSize++;
        int idx = currentSize;
        node[idx] = x;
        indexes[x.vertex] = idx;
        bubbleUp(idx);
    }
    public HeapNode extractMin()
    {
        HeapNode min = node[1];
        HeapNode lastNode = node[currentSize];
        indexes[lastNode.vertex] = 1;
        node[1] = lastNode;
        node[currentSize] = null;
        sinkDown(1);
        currentSize--;
        return min;
    }
    public void sinkDown(int k)
    {
        int smallest = k;
        // left child
        int leftChild = 2 *k;
        // right child
        int rightChild = 2 *k + 1;
        if (leftChild < heapSize() 
            && node[smallest].key > node[leftChild].key)
        {
            smallest = leftChild;
        }
        if (rightChild < heapSize() 
            && node[smallest].key > node[rightChild].key)
        {
            smallest = rightChild;
        }
        if (smallest != k)
        {
            HeapNode smallestNode = node[smallest];
            HeapNode kNode = node[k];
            indexes[smallestNode.vertex] = k;
            indexes[kNode.vertex] = smallest;
            swap(k, smallest);
            sinkDown(smallest);
        }
    }
}
public class Graph
{
    int vertices;
    public ArrayList < ArrayList < Edge >> adjacencylist;
    public Graph(int vertices)
    {
        this.vertices = vertices;
        this.adjacencylist = new ArrayList < ArrayList < Edge >> (vertices);
        for (int i = 0; i < this.vertices; ++i)
        {
            this.adjacencylist.add(new ArrayList < Edge > ());
        }
    }
    public void addEdge(int u, int v, int weight)
    {
        adjacencylist.get(u).add(new Edge(u, v, weight));
        if (u == v)
        {
            // self loop
            return;
        }
        adjacencylist.get(v).add(new Edge(v, u, weight));
    }
    public void decreaseKey(MinHeap minHeap, int newKey, int vertex)
    {
        int index = minHeap.indexes[vertex];
        HeapNode node = minHeap.node[index];
        node.key = newKey;
        minHeap.bubbleUp(index);
    }
    public void primMST()
    {
        boolean[] inHeap = new boolean[this.vertices];
        ResultSet[] resultSet = new ResultSet[this.vertices];
        int[] key = new int[this.vertices];
        HeapNode[] heapNodes = new HeapNode[this.vertices];
        // Set default value of heap nodes resultset and keys
        for (int i = 0; i < this.vertices; i++)
        {
            heapNodes[i] = new HeapNode();
            heapNodes[i].vertex = i;
            heapNodes[i].key = Integer.MAX_VALUE;
            resultSet[i] = new ResultSet();
            resultSet[i].parent = -1;
            inHeap[i] = true;
            key[i] = Integer.MAX_VALUE;
        }
        heapNodes[0].key = 0;
        MinHeap minHeap = new MinHeap(this.vertices);
        for (int j = 0; j < this.vertices; j++)
        {
            minHeap.insert(heapNodes[j]);
        }
        int i = 0;
        while (minHeap.isEmpty() == false)
        {
            HeapNode extractedNode = minHeap.extractMin();
            int extractedVertex = extractedNode.vertex;
            inHeap[extractedVertex] = false;
            while (i < adjacencylist.get(extractedVertex).size())
            {
                Edge edge = adjacencylist.get(extractedVertex).get(i);
                if (inHeap[edge.v])
                {
                    int v = edge.v;
                    int w = edge.weight;
                    if (key[v] > w)
                    {
                        key[v] = w;
                        decreaseKey(minHeap, w, v);
                        resultSet[v].parent = extractedVertex;
                        resultSet[v].weight = w;
                    }
                }
                i++;
            }
            i = 0;
        }
        int result = 0;
        System.out.print("\n\n Minimum Spanning Tree \n");
        for (int node = 1; node < this.vertices; ++node)
        {
            System.out.println(" Edge (" + resultSet[node].parent + 
                               "-" + node + ")  weight : " + 
                               resultSet[node].weight);
            result += resultSet[node].weight;
        }
        // Display calculated result
        System.out.println(" Total minimum weight : " + result);
    }
    // Display graph nodes and edges
    public void printGraph()
    {
        System.out.print("\n Graph Adjacency List ");
        for (int i = 0; i < this.vertices; ++i)
        {
            System.out.print(" \n [" + i + "] :");
            // iterate edges of i node
            for (int j = 0; j < this.adjacencylist.get(i).size(); ++j)
            {
                System.out.print("  " + this.adjacencylist.get(i).get(j).v);
            }
        }
    }
    public static void main(String[] args)
    {
        Graph g = new Graph(10);
        g.addEdge(0, 1, 7);
        g.addEdge(0, 7, 6);
        g.addEdge(0, 8, 4);
        g.addEdge(1, 2, 9);
        g.addEdge(1, 8, 6);
        g.addEdge(2, 3, 8);
        g.addEdge(2, 6, 12);
        g.addEdge(2, 9, 14);
        g.addEdge(3, 4, 16);
        g.addEdge(3, 9, 5);
        g.addEdge(4, 5, 15);
        g.addEdge(5, 6, 8);
        g.addEdge(5, 9, 7);
        g.addEdge(6, 7, 2);
        g.addEdge(6, 8, 10);
        g.addEdge(8, 9, 3);
        // Display graph element
        g.printGraph();
        g.primMST();
    }
}

input

 Graph Adjacency List
 [0] :  1  7  8
 [1] :  0  2  8
 [2] :  1  3  6  9
 [3] :  2  4  9
 [4] :  3  5
 [5] :  4  6  9
 [6] :  2  5  7  8
 [7] :  0  6
 [8] :  0  1  6  9
 [9] :  2  3  5  8

 Minimum Spanning Tree
 Edge (8-1)  weight : 6
 Edge (3-2)  weight : 8
 Edge (9-3)  weight : 5
 Edge (5-4)  weight : 15
 Edge (9-5)  weight : 7
 Edge (7-6)  weight : 2
 Edge (0-7)  weight : 6
 Edge (0-8)  weight : 4
 Edge (8-9)  weight : 3
 Total minimum weight : 56
// Include header file
#include <iostream>
#include <limits.h>
#include <vector>

using namespace std;
/*
    C++ program for
    Prim's algorithm using adjacency list
*/
class Edge
{
    public:
    // Source node
    int u;
    // Destination node
    int v;
    // Edge weight
    int weight;
    Edge(int u, int v, int weight)
    {
        this->u = u;
        this->v = v;
        this->weight = weight;
    }
};
class HeapNode
{
    public: int vertex;
    int key;
};
class ResultSet
{
    public: int parent;
    int weight;
};
class MinHeap
{
    public: int capacity;
    int currentSize;
    HeapNode **node;
    int *indexes;
    MinHeap(int capacity)
    {
        this->capacity = capacity;
        this->node = new HeapNode*[capacity + 1];
        this->indexes = new int[capacity];
        this->node[0] = new HeapNode();
        this->node[0]->key = INT_MIN;
        this->node[0]->vertex = -1;
        this->currentSize = 0;
    }
    void swap(int a, int b)
    {
        HeapNode *temp = this->node[a];
        this->node[a] = this->node[b];
        this->node[b] = temp;
    }
    bool isEmpty()
    {
        return this->currentSize == 0;
    }
    int heapSize()
    {
        return this->currentSize;
    }
    void bubbleUp(int pos)
    {
        int parentIdx = pos / 2;
        int currentIdx = pos;
        while (currentIdx > 0 
               && this->node[parentIdx]->key > this->node[currentIdx]->key)
        {
            HeapNode *currentNode = this->node[currentIdx];
            HeapNode *parentNode = this->node[parentIdx];
            this->indexes[currentNode->vertex] = parentIdx;
            this->indexes[parentNode->vertex] = currentIdx;
            this->swap(currentIdx, parentIdx);
            currentIdx = parentIdx;
            parentIdx = parentIdx / 2;
        }
    }
    void insert(HeapNode *x)
    {
        this->currentSize++;
        int idx = this->currentSize;
        this->node[idx] = x;
        this->indexes[x->vertex] = idx;
        this->bubbleUp(idx);
    }
    HeapNode *extractMin()
    {
        HeapNode *min = this->node[1];
        HeapNode *lastNode = this->node[this->currentSize];
        this->indexes[lastNode->vertex] = 1;
        this->node[1] = lastNode;
        this->node[this->currentSize] = NULL;
        this->sinkDown(1);
        this->currentSize--;
        return min;
    }
    void sinkDown(int k)
    {
        int smallest = k;
        // left child
        int leftChild = 2 *k;
        // right child
        int rightChild = 2 *k + 1;
        if (leftChild < this->heapSize() 
            && this->node[smallest]->key > this->node[leftChild]->key)
        {
            smallest = leftChild;
        }
        if (rightChild < this->heapSize() 
            && this->node[smallest]->key > this->node[rightChild]->key)
        {
            smallest = rightChild;
        }
        if (smallest != k)
        {
            HeapNode *smallestNode = this->node[smallest];
            HeapNode *kNode = this->node[k];
            this->indexes[smallestNode->vertex] = k;
            this->indexes[kNode->vertex] = smallest;
            this->swap(k, smallest);
            this->sinkDown(smallest);
        }
    }
};
class Graph
{
    public: int vertices;
    vector < vector < Edge *> > adjacencylist;
    Graph(int vertices)
    {
        this->vertices = vertices;
        for (int i = 0; i < this->vertices; ++i)
        {
            this->adjacencylist.push_back( vector < Edge *> ());
        }
    }
    void addEdge(int u, int v, int weight)
    {
        this->adjacencylist.at(u).push_back(new Edge(u, v, weight));
        if (u == v)
        {
            // self loop
            return;
        }
        this->adjacencylist.at(v).push_back(new Edge(v, u, weight));
    }
    void decreaseKey(MinHeap *minHeap, int newKey, int vertex)
    {
        int index = minHeap->indexes[vertex];
        HeapNode *node = minHeap->node[index];
        node->key = newKey;
        minHeap->bubbleUp(index);
    }
    void primMST()
    {
        bool inHeap[this->vertices];
        ResultSet *resultSet[this->vertices];
        int key[this->vertices];
        HeapNode *heapNodes[this->vertices];
        // Set default value of heap nodes resultset and keys
        for (int i = 0; i < this->vertices; i++)
        {
            heapNodes[i] = new HeapNode();
            heapNodes[i]->vertex = i;
            heapNodes[i]->key = INT_MAX;
            resultSet[i] = new ResultSet();
            resultSet[i]->parent = -1;
            inHeap[i] = true;
            key[i] = INT_MAX;
        }
        heapNodes[0]->key = 0;
        MinHeap *minHeap = new MinHeap(this->vertices);
        for (int j = 0; j < this->vertices; j++)
        {
            minHeap->insert(heapNodes[j]);
        }
        int i = 0;
        while (minHeap->isEmpty() == false)
        {
            HeapNode *extractedNode = minHeap->extractMin();
            int extractedVertex = extractedNode->vertex;
            inHeap[extractedVertex] = false;
            while (i < this->adjacencylist.at(extractedVertex).size())
            {
                Edge *edge = this->adjacencylist.at(extractedVertex).at(i);
                if (inHeap[edge->v])
                {
                    int v = edge->v;
                    int w = edge->weight;
                    if (key[v] > w)
                    {
                        key[v] = w;
                        this->decreaseKey(minHeap, w, v);
                        resultSet[v]->parent = extractedVertex;
                        resultSet[v]->weight = w;
                    }
                }
                i++;
            }
            i = 0;
        }
        int result = 0;
        cout << "\n\n Minimum Spanning Tree \n";
        for (int node = 1; node < this->vertices; ++node)
        {
            cout << " Edge (" << resultSet[node]->parent 
                 << "-" << node << ")  weight : " 
                 << resultSet[node]->weight << endl;
            result += resultSet[node]->weight;
        }
        // Display calculated result
        cout << " Total minimum weight : " << result << endl;
    }
    // Display graph nodes and edges
    void printGraph()
    {
        cout << "\n Graph Adjacency List ";
        for (int i = 0; i < this->vertices; ++i)
        {
            cout << " \n [" << i << "] :";
            // iterate edges of i node
            for (int j = 0; j < this->adjacencylist.at(i).size(); ++j)
            {
                cout << "  " << this->adjacencylist.at(i).at(j)->v;
            }
        }
    }
};
int main()
{
    Graph *g = new Graph(10);
    g->addEdge(0, 1, 7);
    g->addEdge(0, 7, 6);
    g->addEdge(0, 8, 4);
    g->addEdge(1, 2, 9);
    g->addEdge(1, 8, 6);
    g->addEdge(2, 3, 8);
    g->addEdge(2, 6, 12);
    g->addEdge(2, 9, 14);
    g->addEdge(3, 4, 16);
    g->addEdge(3, 9, 5);
    g->addEdge(4, 5, 15);
    g->addEdge(5, 6, 8);
    g->addEdge(5, 9, 7);
    g->addEdge(6, 7, 2);
    g->addEdge(6, 8, 10);
    g->addEdge(8, 9, 3);
    // Display graph element
    g->printGraph();
    g->primMST();
    return 0;
}

input

 Graph Adjacency List
 [0] :  1  7  8
 [1] :  0  2  8
 [2] :  1  3  6  9
 [3] :  2  4  9
 [4] :  3  5
 [5] :  4  6  9
 [6] :  2  5  7  8
 [7] :  0  6
 [8] :  0  1  6  9
 [9] :  2  3  5  8

 Minimum Spanning Tree
 Edge (8-1)  weight : 6
 Edge (3-2)  weight : 8
 Edge (9-3)  weight : 5
 Edge (5-4)  weight : 15
 Edge (9-5)  weight : 7
 Edge (7-6)  weight : 2
 Edge (0-7)  weight : 6
 Edge (0-8)  weight : 4
 Edge (8-9)  weight : 3
 Total minimum weight : 56
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program for
    Prim's algorithm using adjacency list
*/
public class Edge
{
    // Source node
    public int u;
    // Destination node
    public int v;
    // Edge weight
    public int weight;
    public Edge(int u, int v, int weight)
    {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }
}
public class HeapNode
{
    public int vertex;
    public int key;
}
public class ResultSet
{
    public int parent;
    public int weight;
}
public class MinHeap
{
    int capacity;
    int currentSize;
    public HeapNode[] node;
    public int[] indexes;
    public MinHeap(int capacity)
    {
        this.capacity = capacity;
        this.node = new HeapNode[this.capacity + 1];
        this.indexes = new int[this.capacity];
        this.node[0] = new HeapNode();
        this.node[0].key = int.MinValue;
        this.node[0].vertex = -1;
        this.currentSize = 0;
    }
    public void swap(int a, int b)
    {
        HeapNode temp = this.node[a];
        this.node[a] = this.node[b];
        this.node[b] = temp;
    }
    public Boolean isEmpty()
    {
        return this.currentSize == 0;
    }
    public int heapSize()
    {
        return this.currentSize;
    }
    public void bubbleUp(int pos)
    {
        int parentIdx = pos / 2;
        int currentIdx = pos;
        while (currentIdx > 0 
               && this.node[parentIdx].key > this.node[currentIdx].key)
        {
            HeapNode currentNode = this.node[currentIdx];
            HeapNode parentNode = this.node[parentIdx];
            this.indexes[currentNode.vertex] = parentIdx;
            this.indexes[parentNode.vertex] = currentIdx;
            this.swap(currentIdx, parentIdx);
            currentIdx = parentIdx;
            parentIdx = parentIdx / 2;
        }
    }
    public void insert(HeapNode x)
    {
        this.currentSize++;
        int idx = this.currentSize;
        this.node[idx] = x;
        this.indexes[x.vertex] = idx;
        this.bubbleUp(idx);
    }
    public HeapNode extractMin()
    {
        HeapNode min = this.node[1];
        HeapNode lastNode = this.node[this.currentSize];
        this.indexes[lastNode.vertex] = 1;
        this.node[1] = lastNode;
        this.node[this.currentSize] = null;
        this.sinkDown(1);
        this.currentSize--;
        return min;
    }
    public void sinkDown(int k)
    {
        int smallest = k;
        // left child
        int leftChild = 2 * k;
        // right child
        int rightChild = 2 * k + 1;
        if (leftChild < this.heapSize() 
            && this.node[smallest].key > this.node[leftChild].key)
        {
            smallest = leftChild;
        }
        if (rightChild < this.heapSize() 
            && this.node[smallest].key > this.node[rightChild].key)
        {
            smallest = rightChild;
        }
        if (smallest != k)
        {
            HeapNode smallestNode = this.node[smallest];
            HeapNode kNode = this.node[k];
            this.indexes[smallestNode.vertex] = k;
            this.indexes[kNode.vertex] = smallest;
            this.swap(k, smallest);
            this.sinkDown(smallest);
        }
    }
}
public class Graph
{
    int vertices;
    public List < List < Edge >> adjacencylist;
    public Graph(int vertices)
    {
        this.vertices = vertices;
        this.adjacencylist = new List < List < Edge >> (vertices);
        for (int i = 0; i < this.vertices; ++i)
        {
            this.adjacencylist.Add(new List < Edge > ());
        }
    }
    public void addEdge(int u, int v, int weight)
    {
        this.adjacencylist[u].Add(new Edge(u, v, weight));
        if (u == v)
        {
            // self loop
            return;
        }
        this.adjacencylist[v].Add(new Edge(v, u, weight));
    }
    public void decreaseKey(MinHeap minHeap, int newKey, int vertex)
    {
        int index = minHeap.indexes[vertex];
        HeapNode node = minHeap.node[index];
        node.key = newKey;
        minHeap.bubbleUp(index);
    }
    public void primMST()
    {
        Boolean[] inHeap = new Boolean[this.vertices];
        ResultSet[] resultSet = new ResultSet[this.vertices];
        int[] key = new int[this.vertices];
        HeapNode[] heapNodes = new HeapNode[this.vertices];
        // Set default value of heap nodes resultset and keys
        for (int i = 0; i < this.vertices; i++)
        {
            heapNodes[i] = new HeapNode();
            heapNodes[i].vertex = i;
            heapNodes[i].key = int.MaxValue;
            resultSet[i] = new ResultSet();
            resultSet[i].parent = -1;
            inHeap[i] = true;
            key[i] = int.MaxValue;
        }
        heapNodes[0].key = 0;
        MinHeap minHeap = new MinHeap(this.vertices);
        for (int j = 0; j < this.vertices; j++)
        {
            minHeap.insert(heapNodes[j]);
        }
        int k = 0;
        while (minHeap.isEmpty() == false)
        {
            HeapNode extractedNode = minHeap.extractMin();
            int extractedVertex = extractedNode.vertex;
            inHeap[extractedVertex] = false;
            while (k < this.adjacencylist[extractedVertex].Count)
            {
                Edge edge = this.adjacencylist[extractedVertex][k];
                if (inHeap[edge.v])
                {
                    int v = edge.v;
                    int w = edge.weight;
                    if (key[v] > w)
                    {
                        key[v] = w;
                        this.decreaseKey(minHeap, w, v);
                        resultSet[v].parent = extractedVertex;
                        resultSet[v].weight = w;
                    }
                }
                k++;
            }
            k = 0;
        }
        int result = 0;
        Console.Write("\n\n Minimum Spanning Tree \n");
        for (int node = 1; node < this.vertices; ++node)
        {
            Console.WriteLine(" Edge (" + resultSet[node].parent + 
                              "-" + node + ")  weight : " + 
                              resultSet[node].weight);
            result += resultSet[node].weight;
        }
        // Display calculated result
        Console.WriteLine(" Total minimum weight : " + result);
    }
    // Display graph nodes and edges
    public void printGraph()
    {
        Console.Write("\n Graph Adjacency List ");
        for (int i = 0; i < this.vertices; ++i)
        {
            Console.Write(" \n [" + i + "] :");
            // iterate edges of i node
            for (int j = 0; j < this.adjacencylist[i].Count; ++j)
            {
                Console.Write("  " + this.adjacencylist[i][j].v);
            }
        }
    }
    public static void Main(String[] args)
    {
        Graph g = new Graph(10);
        g.addEdge(0, 1, 7);
        g.addEdge(0, 7, 6);
        g.addEdge(0, 8, 4);
        g.addEdge(1, 2, 9);
        g.addEdge(1, 8, 6);
        g.addEdge(2, 3, 8);
        g.addEdge(2, 6, 12);
        g.addEdge(2, 9, 14);
        g.addEdge(3, 4, 16);
        g.addEdge(3, 9, 5);
        g.addEdge(4, 5, 15);
        g.addEdge(5, 6, 8);
        g.addEdge(5, 9, 7);
        g.addEdge(6, 7, 2);
        g.addEdge(6, 8, 10);
        g.addEdge(8, 9, 3);
        // Display graph element
        g.printGraph();
        g.primMST();
    }
}

input

 Graph Adjacency List
 [0] :  1  7  8
 [1] :  0  2  8
 [2] :  1  3  6  9
 [3] :  2  4  9
 [4] :  3  5
 [5] :  4  6  9
 [6] :  2  5  7  8
 [7] :  0  6
 [8] :  0  1  6  9
 [9] :  2  3  5  8

 Minimum Spanning Tree
 Edge (8-1)  weight : 6
 Edge (3-2)  weight : 8
 Edge (9-3)  weight : 5
 Edge (5-4)  weight : 15
 Edge (9-5)  weight : 7
 Edge (7-6)  weight : 2
 Edge (0-7)  weight : 6
 Edge (0-8)  weight : 4
 Edge (8-9)  weight : 3
 Total minimum weight : 56
<?php
/*
    Php program for
    Prim's algorithm using adjacency list
*/
class Edge
{
    // Source node
    public $u;
    // Destination node
    public $v;
    // Edge weight
    public $weight;
    public  function __construct($u, $v, $weight)
    {
        $this->u = $u;
        $this->v = $v;
        $this->weight = $weight;
    }
}
class HeapNode
{
    public $vertex;
    public $key;
}
class ResultSet
{
    public $parent;
    public $weight;
}
class MinHeap
{
    public $capacity;
    public $currentSize;
    public $node;
    public $indexes;
    public  function __construct($capacity)
    {
        $this->capacity = $capacity;
        $this->node = array_fill(0, $capacity + 1, NULL);
        $this->indexes = array_fill(0, $capacity, 0);
        $this->node[0] = new HeapNode();
        $this->node[0]->key = -PHP_INT_MAX;
        $this->node[0]->vertex = -1;
        $this->currentSize = 0;
    }
    public  function swap($a, $b)
    {
        $temp = $this->node[$a];
        $this->node[$a] = $this->node[$b];
        $this->node[$b] = $temp;
    }
    public  function isEmpty()
    {
        return $this->currentSize == 0;
    }
    public  function heapSize()
    {
        return $this->currentSize;
    }
    public  function bubbleUp($pos)
    {
        $parentIdx = (int)($pos / 2);
        $currentIdx = $pos;
        while ($currentIdx > 0 && $this->node[$parentIdx]->key > $this->node[$currentIdx]->key)
        {
            $currentNode = $this->node[$currentIdx];
            $parentNode = $this->node[$parentIdx];
            $this->indexes[$currentNode->vertex] = $parentIdx;
            $this->indexes[$parentNode->vertex] = $currentIdx;
            $this->swap($currentIdx, $parentIdx);
            $currentIdx = $parentIdx;
            $parentIdx = (int)($parentIdx / 2);
        }
    }
    public  function insert($x)
    {
        $this->currentSize++;
        $idx = $this->currentSize;
        $this->node[$idx] = $x;
        $this->indexes[$x->vertex] = $idx;
        $this->bubbleUp($idx);
    }
    public  function extractMin()
    {
        $min = $this->node[1];
        $lastNode = $this->node[$this->currentSize];
        $this->indexes[$lastNode->vertex] = 1;
        $this->node[1] = $lastNode;
        $this->node[$this->currentSize] = NULL;
        $this->sinkDown(1);
        $this->currentSize--;
        return $min;
    }
    public  function sinkDown($k)
    {
        $smallest = $k;
        // left child
        $leftChild = 2 * $k;
        // right child
        $rightChild = 2 * $k + 1;
        if ($leftChild < $this->heapSize() && $this->node[$smallest]->key > $this->node[$leftChild]->key)
        {
            $smallest = $leftChild;
        }
        if ($rightChild < $this->heapSize() && $this->node[$smallest]->key > $this->node[$rightChild]->key)
        {
            $smallest = $rightChild;
        }
        if ($smallest != $k)
        {
            $smallestNode = $this->node[$smallest];
            $kNode = $this->node[$k];
            $this->indexes[$smallestNode->vertex] = $k;
            $this->indexes[$kNode->vertex] = $smallest;
            $this->swap($k, $smallest);
            $this->sinkDown($smallest);
        }
    }
}
class Graph
{
    public $vertices;
    public $adjacencylist;
    public  function __construct($vertices)
    {
        $this->vertices = $vertices;
        $this->adjacencylist = array();
        for ($i = 0; $i < $this->vertices; ++$i)
        {
            $this->adjacencylist[] = array();
        }
    }
    public  function addEdge($u, $v, $weight)
    {
        $this->adjacencylist[$u][] = new Edge($u, $v, $weight);
        if ($u == $v)
        {
            // self loop
            return;
        }
        $this->adjacencylist[$v][] = new Edge($v, $u, $weight);
    }
    public  function decreaseKey($minHeap, $newKey, $vertex)
    {
        $index = $minHeap->indexes[$vertex];
        $node = $minHeap->node[$index];
        $node->key = $newKey;
        $minHeap->bubbleUp($index);
    }
    public  function primMST()
    {
        $inHeap = array_fill(0, $this->vertices, false);
        $resultSet = array_fill(0, $this->vertices, NULL);
        $key = array_fill(0, $this->vertices, 0);
        $heapNodes = array_fill(0, $this->vertices, NULL);
        // Set default value of heap nodes resultset and keys
        for ($i = 0; $i < $this->vertices; $i++)
        {
            $heapNodes[$i] = new HeapNode();
            $heapNodes[$i]->vertex = $i;
            $heapNodes[$i]->key = PHP_INT_MAX;
            $resultSet[$i] = new ResultSet();
            $resultSet[$i]->parent = -1;
            $inHeap[$i] = true;
            $key[$i] = PHP_INT_MAX;
        }
        $heapNodes[0]->key = 0;
        $minHeap = new MinHeap($this->vertices);
        for ($j = 0; $j < $this->vertices; $j++)
        {
            $minHeap->insert($heapNodes[$j]);
        }
        $i = 0;
        while ($minHeap->isEmpty() == false)
        {
            $extractedNode = $minHeap->extractMin();
            $extractedVertex = $extractedNode->vertex;
            $inHeap[$extractedVertex] = false;
            while ($i < count($this->adjacencylist[$extractedVertex]))
            {
                $edge = $this->adjacencylist[$extractedVertex][$i];
                if ($inHeap[$edge->v])
                {
                    $v = $edge->v;
                    $w = $edge->weight;
                    if ($key[$v] > $w)
                    {
                        $key[$v] = $w;
                        $this->decreaseKey($minHeap, $w, $v);
                        $resultSet[$v]->parent = $extractedVertex;
                        $resultSet[$v]->weight = $w;
                    }
                }
                $i++;
            }
            $i = 0;
        }
        $result = 0;
        echo("\n\n Minimum Spanning Tree \n");
        for ($node = 1; $node < $this->vertices; ++$node)
        {
            echo(" Edge (".$resultSet[$node]->parent.
                "-".$node.
                ")  weight : ".$resultSet[$node]->weight.
                "\n");
            $result += $resultSet[$node]->weight;
        }
        // Display calculated result
        echo(" Total minimum weight : ".$result.
            "\n");
    }
    // Display graph nodes and edges
    public  function printGraph()
    {
        echo("\n Graph Adjacency List ");
        for ($i = 0; $i < $this->vertices; ++$i)
        {
            echo(" \n [".$i."] :");
            // iterate edges of i node
            for ($j = 0; $j < count($this->adjacencylist[$i]); ++$j)
            {
                echo("  ".$this->adjacencylist[$i][$j]->v);
            }
        }
    }
}

function main()
{
    $g = new Graph(10);
    $g->addEdge(0, 1, 7);
    $g->addEdge(0, 7, 6);
    $g->addEdge(0, 8, 4);
    $g->addEdge(1, 2, 9);
    $g->addEdge(1, 8, 6);
    $g->addEdge(2, 3, 8);
    $g->addEdge(2, 6, 12);
    $g->addEdge(2, 9, 14);
    $g->addEdge(3, 4, 16);
    $g->addEdge(3, 9, 5);
    $g->addEdge(4, 5, 15);
    $g->addEdge(5, 6, 8);
    $g->addEdge(5, 9, 7);
    $g->addEdge(6, 7, 2);
    $g->addEdge(6, 8, 10);
    $g->addEdge(8, 9, 3);
    // Display graph element
    $g->printGraph();
    $g->primMST();
}
main();

input

 Graph Adjacency List
 [0] :  1  7  8
 [1] :  0  2  8
 [2] :  1  3  6  9
 [3] :  2  4  9
 [4] :  3  5
 [5] :  4  6  9
 [6] :  2  5  7  8
 [7] :  0  6
 [8] :  0  1  6  9
 [9] :  2  3  5  8

 Minimum Spanning Tree
 Edge (8-1)  weight : 6
 Edge (3-2)  weight : 8
 Edge (9-3)  weight : 5
 Edge (5-4)  weight : 15
 Edge (9-5)  weight : 7
 Edge (7-6)  weight : 2
 Edge (0-7)  weight : 6
 Edge (0-8)  weight : 4
 Edge (8-9)  weight : 3
 Total minimum weight : 56
/*
    Node JS program for
    Prim's algorithm using adjacency list
*/
class Edge
{
    constructor(u, v, weight)
    {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }
}
class HeapNode
{
    constructor()
    {
        this.vertex = 0;
        this.key = 0;
    }
}
class ResultSet
{
    constructor()
    {
        this.parent = 0;
        this.weight = 0;
    }
}
class MinHeap
{
    constructor(capacity)
    {
        this.capacity = capacity;
        this.node = Array(capacity + 1).fill(null);
        this.indexes = Array(capacity).fill(0);
        this.node[0] = new HeapNode();
        this.node[0].key = -Number.MAX_VALUE;
        this.node[0].vertex = -1;
        this.currentSize = 0;
    }
    swap(a, b)
    {
        var temp = this.node[a];
        this.node[a] = this.node[b];
        this.node[b] = temp;
    }
    isEmpty()
    {
        return this.currentSize == 0;
    }
    heapSize()
    {
        return this.currentSize;
    }
    bubbleUp(pos)
    {
        var parentIdx = parseInt(pos / 2);
        var currentIdx = pos;
        while (currentIdx > 0 
               && this.node[parentIdx].key > this.node[currentIdx].key)
        {
            var currentNode = this.node[currentIdx];
            var parentNode = this.node[parentIdx];
            this.indexes[currentNode.vertex] = parentIdx;
            this.indexes[parentNode.vertex] = currentIdx;
            this.swap(currentIdx, parentIdx);
            currentIdx = parentIdx;
            parentIdx = parseInt(parentIdx / 2);
        }
    }
    insert(x)
    {
        this.currentSize++;
        var idx = this.currentSize;
        this.node[idx] = x;
        this.indexes[x.vertex] = idx;
        this.bubbleUp(idx);
    }
    extractMin()
    {
        var min = this.node[1];
        var lastNode = this.node[this.currentSize];
        this.indexes[lastNode.vertex] = 1;
        this.node[1] = lastNode;
        this.node[this.currentSize] = null;
        this.sinkDown(1);
        this.currentSize--;
        return min;
    }
    sinkDown(k)
    {
        var smallest = k;
        // left child
        var leftChild = 2 * k;
        // right child
        var rightChild = 2 * k + 1;
        if (leftChild < this.heapSize() 
            && this.node[smallest].key > this.node[leftChild].key)
        {
            smallest = leftChild;
        }
        if (rightChild < this.heapSize() 
            && this.node[smallest].key > this.node[rightChild].key)
        {
            smallest = rightChild;
        }
        if (smallest != k)
        {
            var smallestNode = this.node[smallest];
            var kNode = this.node[k];
            this.indexes[smallestNode.vertex] = k;
            this.indexes[kNode.vertex] = smallest;
            this.swap(k, smallest);
            this.sinkDown(smallest);
        }
    }
}
class Graph
{
    constructor(vertices)
    {
        this.vertices = vertices;
        this.adjacencylist = [];
        for (var i = 0; i < this.vertices; ++i)
        {
            this.adjacencylist.push([]);
        }
    }
    addEdge(u, v, weight)
    {
        this.adjacencylist[u].push(new Edge(u, v, weight));
        if (u == v)
        {
            // self loop
            return;
        }
        this.adjacencylist[v].push(new Edge(v, u, weight));
    }
    decreaseKey(minHeap, newKey, vertex)
    {
        var index = minHeap.indexes[vertex];
        var node = minHeap.node[index];
        node.key = newKey;
        minHeap.bubbleUp(index);
    }
    primMST()
    {
        var inHeap = Array(this.vertices).fill(false);
        var resultSet = Array(this.vertices).fill(null);
        var key = Array(this.vertices).fill(0);
        var heapNodes = Array(this.vertices).fill(null);
        // Set default value of heap nodes resultset and keys
        for (var i = 0; i < this.vertices; i++)
        {
            heapNodes[i] = new HeapNode();
            heapNodes[i].vertex = i;
            heapNodes[i].key = Number.MAX_VALUE;
            resultSet[i] = new ResultSet();
            resultSet[i].parent = -1;
            inHeap[i] = true;
            key[i] = Number.MAX_VALUE;
        }
        heapNodes[0].key = 0;
        var minHeap = new MinHeap(this.vertices);
        for (var j = 0; j < this.vertices; j++)
        {
            minHeap.insert(heapNodes[j]);
        }
        var i = 0;
        while (minHeap.isEmpty() == false)
        {
            var extractedNode = minHeap.extractMin();
            var extractedVertex = extractedNode.vertex;
            inHeap[extractedVertex] = false;
            while (i < this.adjacencylist[extractedVertex].length)
            {
                var edge = this.adjacencylist[extractedVertex][i];
                if (inHeap[edge.v])
                {
                    var v = edge.v;
                    var w = edge.weight;
                    if (key[v] > w)
                    {
                        key[v] = w;
                        this.decreaseKey(minHeap, w, v);
                        resultSet[v].parent = extractedVertex;
                        resultSet[v].weight = w;
                    }
                }
                i++;
            }
            i = 0;
        }
        var result = 0;
        process.stdout.write("\n\n Minimum Spanning Tree \n");
        for (var node = 1; node < this.vertices; ++node)
        {
            console.log(" Edge (" + resultSet[node].parent + 
                        "-" + node + ")  weight : " + resultSet[node].weight);
            result += resultSet[node].weight;
        }
        // Display calculated result
        console.log(" Total minimum weight : " + result);
    }
    // Display graph nodes and edges
    printGraph()
    {
        process.stdout.write("\n Graph Adjacency List ");
        for (var i = 0; i < this.vertices; ++i)
        {
            process.stdout.write(" \n [" + i + "] :");
            // iterate edges of i node
            for (var j = 0; j < this.adjacencylist[i].length; ++j)
            {
                process.stdout.write("  " + this.adjacencylist[i][j].v);
            }
        }
    }
}

function main()
{
    var g = new Graph(10);
    g.addEdge(0, 1, 7);
    g.addEdge(0, 7, 6);
    g.addEdge(0, 8, 4);
    g.addEdge(1, 2, 9);
    g.addEdge(1, 8, 6);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 6, 12);
    g.addEdge(2, 9, 14);
    g.addEdge(3, 4, 16);
    g.addEdge(3, 9, 5);
    g.addEdge(4, 5, 15);
    g.addEdge(5, 6, 8);
    g.addEdge(5, 9, 7);
    g.addEdge(6, 7, 2);
    g.addEdge(6, 8, 10);
    g.addEdge(8, 9, 3);
    // Display graph element
    g.printGraph();
    g.primMST();
}
main();

input

 Graph Adjacency List
 [0] :  1  7  8
 [1] :  0  2  8
 [2] :  1  3  6  9
 [3] :  2  4  9
 [4] :  3  5
 [5] :  4  6  9
 [6] :  2  5  7  8
 [7] :  0  6
 [8] :  0  1  6  9
 [9] :  2  3  5  8

 Minimum Spanning Tree
 Edge (8-1)  weight : 6
 Edge (3-2)  weight : 8
 Edge (9-3)  weight : 5
 Edge (5-4)  weight : 15
 Edge (9-5)  weight : 7
 Edge (7-6)  weight : 2
 Edge (0-7)  weight : 6
 Edge (0-8)  weight : 4
 Edge (8-9)  weight : 3
 Total minimum weight : 56
import sys
#    Python 3 program for
#    Prim's algorithm using adjacency list
class Edge :
    #  Source node
    #  Destination node
    #  Edge weight
    def __init__(self, u, v, weight) :
        self.u = u
        self.v = v
        self.weight = weight
    

class HeapNode :
    def __init__(self) :
        self.vertex = 0
        self.key = 0
    

class ResultSet :
    def __init__(self) :
        self.parent = 0
        self.weight = 0
    

class MinHeap :
    def __init__(self, capacity) :
        self.capacity = capacity
        self.node = [None] * (capacity + 1)
        self.indexes = [0] * (capacity)
        self.node[0] = HeapNode()
        self.node[0].key = -sys.maxsize
        self.node[0].vertex = -1
        self.currentSize = 0
    
    def swap(self, a, b) :
        temp = self.node[a]
        self.node[a] = self.node[b]
        self.node[b] = temp
    
    def isEmpty(self) :
        return self.currentSize == 0
    
    def heapSize(self) :
        return self.currentSize
    
    def bubbleUp(self, pos) :
        parentIdx = int(pos / 2)
        currentIdx = pos
        while (currentIdx > 0 and 
               self.node[parentIdx].key > self.node[currentIdx].key) :
            currentNode = self.node[currentIdx]
            parentNode = self.node[parentIdx]
            self.indexes[currentNode.vertex] = parentIdx
            self.indexes[parentNode.vertex] = currentIdx
            self.swap(currentIdx, parentIdx)
            currentIdx = parentIdx
            parentIdx = int(parentIdx / 2)
        
    
    def insert(self, x) :
        self.currentSize += 1
        idx = self.currentSize
        self.node[idx] = x
        self.indexes[x.vertex] = idx
        self.bubbleUp(idx)
    
    def extractMin(self) :
        min = self.node[1]
        lastNode = self.node[self.currentSize]
        self.indexes[lastNode.vertex] = 1
        self.node[1] = lastNode
        self.node[self.currentSize] = None
        self.sinkDown(1)
        self.currentSize -= 1
        return min
    
    def sinkDown(self, k) :
        smallest = k
        #  left child
        leftChild = 2 * k
        #  right child
        rightChild = 2 * k + 1
        if (leftChild < self.heapSize() and 
            self.node[smallest].key > self.node[leftChild].key) :
            smallest = leftChild
        
        if (rightChild < self.heapSize() and 
            self.node[smallest].key > self.node[rightChild].key) :
            smallest = rightChild
        
        if (smallest != k) :
            smallestNode = self.node[smallest]
            kNode = self.node[k]
            self.indexes[smallestNode.vertex] = k
            self.indexes[kNode.vertex] = smallest
            self.swap(k, smallest)
            self.sinkDown(smallest)
        
    

class Graph :
    def __init__(self, vertices) :
        self.vertices = vertices
        self.adjacencylist = []
        i = 0
        while (i < self.vertices) :
            self.adjacencylist.append([])
            i += 1
        
    
    def addEdge(self, u, v, weight) :
        self.adjacencylist[u].append(Edge(u, v, weight))
        if (u == v) :
            #  self loop
            return
        
        self.adjacencylist[v].append(Edge(v, u, weight))
    
    def decreaseKey(self, minHeap, newKey, vertex) :
        index = minHeap.indexes[vertex]
        node = minHeap.node[index]
        node.key = newKey
        minHeap.bubbleUp(index)
    
    def primMST(self) :
        inHeap = [False] * (self.vertices)
        resultSet = [None] * (self.vertices)
        key = [0] * (self.vertices)
        heapNodes = [None] * (self.vertices)
        i = 0
        #  Set default value of heap nodes resultset and keys
        while (i < self.vertices) :
            heapNodes[i] = HeapNode()
            heapNodes[i].vertex = i
            heapNodes[i].key = sys.maxsize
            resultSet[i] = ResultSet()
            resultSet[i].parent = -1
            inHeap[i] = True
            key[i] = sys.maxsize
            i += 1
        
        heapNodes[0].key = 0
        minHeap = MinHeap(self.vertices)
        j = 0
        while (j < self.vertices) :
            minHeap.insert(heapNodes[j])
            j += 1
        
        i = 0
        while (minHeap.isEmpty() == False) :
            extractedNode = minHeap.extractMin()
            extractedVertex = extractedNode.vertex
            inHeap[extractedVertex] = False
            while (i < len(self.adjacencylist[extractedVertex])) :
                edge = self.adjacencylist[extractedVertex][i]
                if (inHeap[edge.v]) :
                    v = edge.v
                    w = edge.weight
                    if (key[v] > w) :
                        key[v] = w
                        self.decreaseKey(minHeap, w, v)
                        resultSet[v].parent = extractedVertex
                        resultSet[v].weight = w
                    
                
                i += 1
            
            i = 0
        
        result = 0
        print("\n\n Minimum Spanning Tree ")
        node = 1
        while (node < self.vertices) :
            print(" Edge (", resultSet[node].parent ,"-", node ,
                  ")  weight : ", resultSet[node].weight)
            result += resultSet[node].weight
            node += 1
        
        #  Display calculated result
        print(" Total minimum weight : ", result)
    
    #  Display graph nodes and edges
    def printGraph(self) :
        print("\n Graph Adjacency List ", end = "")
        i = 0
        while (i < self.vertices) :
            print(" \n [", i ,"] :", end = "")
            j = 0
            #  iterate edges of i node
            while (j < len(self.adjacencylist[i])) :
                print("  ", self.adjacencylist[i][j].v, end = "")
                j += 1
            
            i += 1
        
    

def main() :
    g = Graph(10)
    g.addEdge(0, 1, 7)
    g.addEdge(0, 7, 6)
    g.addEdge(0, 8, 4)
    g.addEdge(1, 2, 9)
    g.addEdge(1, 8, 6)
    g.addEdge(2, 3, 8)
    g.addEdge(2, 6, 12)
    g.addEdge(2, 9, 14)
    g.addEdge(3, 4, 16)
    g.addEdge(3, 9, 5)
    g.addEdge(4, 5, 15)
    g.addEdge(5, 6, 8)
    g.addEdge(5, 9, 7)
    g.addEdge(6, 7, 2)
    g.addEdge(6, 8, 10)
    g.addEdge(8, 9, 3)
    #  Display graph element
    g.printGraph()
    g.primMST()

if __name__ == "__main__": main()

input

 Graph Adjacency List
 [ 0 ] :   1   7   8
 [ 1 ] :   0   2   8
 [ 2 ] :   1   3   6   9
 [ 3 ] :   2   4   9
 [ 4 ] :   3   5
 [ 5 ] :   4   6   9
 [ 6 ] :   2   5   7   8
 [ 7 ] :   0   6
 [ 8 ] :   0   1   6   9
 [ 9 ] :   2   3   5   8

 Minimum Spanning Tree
 Edge ( 8 - 1 )  weight :  6
 Edge ( 3 - 2 )  weight :  8
 Edge ( 9 - 3 )  weight :  5
 Edge ( 5 - 4 )  weight :  15
 Edge ( 9 - 5 )  weight :  7
 Edge ( 7 - 6 )  weight :  2
 Edge ( 0 - 7 )  weight :  6
 Edge ( 0 - 8 )  weight :  4
 Edge ( 8 - 9 )  weight :  3
 Total minimum weight :  56
#    Ruby program for
#    Prim's algorithm using adjacency list
class Edge 
    # Define the accessor and reader of class Edge
    attr_reader :u, :v, :weight
    attr_accessor :u, :v, :weight
    #  Source node
    #  Destination node
    #  Edge weight
    def initialize(u, v, weight) 
        self.u = u
        self.v = v
        self.weight = weight
    end

end

class HeapNode 
    # Define the accessor and reader of class HeapNode
    attr_reader :vertex, :key
    attr_accessor :vertex, :key
    def initialize() 
        self.vertex = 0
        self.key = 0
    end

end

class ResultSet 
    # Define the accessor and reader of class ResultSet
    attr_reader :parent, :weight
    attr_accessor :parent, :weight
    def initialize() 
        self.parent = 0
        self.weight = 0
    end

end

class MinHeap 
    # Define the accessor and reader of class MinHeap
    attr_reader :capacity, :currentSize, :node, :indexes
    attr_accessor :capacity, :currentSize, :node, :indexes
    def initialize(capacity) 
        self.capacity = capacity
        self.node = Array.new(capacity + 1) {nil}
        self.indexes = Array.new(capacity) {0}
        self.node[0] = HeapNode.new()
        self.node[0].key = -(2 ** (0. size * 8 - 2))
        self.node[0].vertex = -1
        self.currentSize = 0
    end

    def swap(a, b) 
        temp = self.node[a]
        self.node[a] = self.node[b]
        self.node[b] = temp
    end

    def isEmpty() 
        return self.currentSize == 0
    end

    def heapSize() 
        return self.currentSize
    end

    def bubbleUp(pos) 
        parentIdx = pos / 2
        currentIdx = pos
        while (currentIdx > 0 && 
               self.node[parentIdx].key > self.node[currentIdx].key) 
            currentNode = self.node[currentIdx]
            parentNode = self.node[parentIdx]
            self.indexes[currentNode.vertex] = parentIdx
            self.indexes[parentNode.vertex] = currentIdx
            self.swap(currentIdx, parentIdx)
            currentIdx = parentIdx
            parentIdx = parentIdx / 2
        end

    end

    def insert(x) 
        self.currentSize += 1
        idx = self.currentSize
        self.node[idx] = x
        self.indexes[x.vertex] = idx
        self.bubbleUp(idx)
    end

    def extractMin() 
        min = self.node[1]
        lastNode = self.node[self.currentSize]
        self.indexes[lastNode.vertex] = 1
        self.node[1] = lastNode
        self.node[self.currentSize] = nil
        self.sinkDown(1)
        self.currentSize -= 1
        return min
    end

    def sinkDown(k) 
        smallest = k
        #  left child
        leftChild = 2 * k
        #  right child
        rightChild = 2 * k + 1
        if (leftChild < self.heapSize() && 
            self.node[smallest].key > self.node[leftChild].key) 
            smallest = leftChild
        end

        if (rightChild < self.heapSize() && 
            self.node[smallest].key > self.node[rightChild].key) 
            smallest = rightChild
        end

        if (smallest != k) 
            smallestNode = self.node[smallest]
            kNode = self.node[k]
            self.indexes[smallestNode.vertex] = k
            self.indexes[kNode.vertex] = smallest
            self.swap(k, smallest)
            self.sinkDown(smallest)
        end

    end

end

class Graph 
    # Define the accessor and reader of class Graph
    attr_reader :vertices, :adjacencylist
    attr_accessor :vertices, :adjacencylist
    def initialize(vertices) 
        self.vertices = vertices
        self.adjacencylist = []
        i = 0
        while (i < self.vertices) 
            self.adjacencylist.push([])
            i += 1
        end

    end

    def addEdge(u, v, weight) 
        self.adjacencylist[u].push(Edge.new(u, v, weight))
        if (u == v) 
            #  self loop
            return
        end

        self.adjacencylist[v].push(Edge.new(v, u, weight))
    end

    def decreaseKey(minHeap, newKey, vertex) 
        index = minHeap.indexes[vertex]
        node = minHeap.node[index]
        node.key = newKey
        minHeap.bubbleUp(index)
    end

    def primMST() 
        inHeap = Array.new(self.vertices) {false}
        resultSet = Array.new(self.vertices) {nil}
        key = Array.new(self.vertices) {0}
        heapNodes = Array.new(self.vertices) {nil}
        i = 0
        #  Set default value of heap nodes resultset and keys
        while (i < self.vertices) 
            heapNodes[i] = HeapNode.new()
            heapNodes[i].vertex = i
            heapNodes[i].key = (2 ** (0. size * 8 - 2))
            resultSet[i] = ResultSet.new()
            resultSet[i].parent = -1
            inHeap[i] = true
            key[i] = (2 ** (0. size * 8 - 2))
            i += 1
        end

        heapNodes[0].key = 0
        minHeap = MinHeap.new(self.vertices)
        j = 0
        while (j < self.vertices) 
            minHeap.insert(heapNodes[j])
            j += 1
        end

        i = 0
        while (minHeap.isEmpty() == false) 
            extractedNode = minHeap.extractMin()
            extractedVertex = extractedNode.vertex
            inHeap[extractedVertex] = false
            while (i < self.adjacencylist[extractedVertex].length) 
                edge = self.adjacencylist[extractedVertex][i]
                if (inHeap[edge.v]) 
                    v = edge.v
                    w = edge.weight
                    if (key[v] > w) 
                        key[v] = w
                        self.decreaseKey(minHeap, w, v)
                        resultSet[v].parent = extractedVertex
                        resultSet[v].weight = w
                    end

                end

                i += 1
            end

            i = 0
        end

        result = 0
        print("\n\n Minimum Spanning Tree \n")
        node = 1
        while (node < self.vertices) 
            print(" Edge (", resultSet[node].parent ,"-", 
                  node ,")  weight : ", resultSet[node].weight, "\n")
            result += resultSet[node].weight
            node += 1
        end

        #  Display calculated result
        print(" Total minimum weight : ", result, "\n")
    end

    #  Display graph nodes and edges
    def printGraph() 
        print("\n Graph Adjacency List ")
        i = 0
        while (i < self.vertices) 
            print(" \n [", i ,"] :")
            j = 0
            #  iterate edges of i node
            while (j < self.adjacencylist[i].length) 
                print("  ", self.adjacencylist[i][j].v)
                j += 1
            end

            i += 1
        end

    end

end

def main() 
    g = Graph.new(10)
    g.addEdge(0, 1, 7)
    g.addEdge(0, 7, 6)
    g.addEdge(0, 8, 4)
    g.addEdge(1, 2, 9)
    g.addEdge(1, 8, 6)
    g.addEdge(2, 3, 8)
    g.addEdge(2, 6, 12)
    g.addEdge(2, 9, 14)
    g.addEdge(3, 4, 16)
    g.addEdge(3, 9, 5)
    g.addEdge(4, 5, 15)
    g.addEdge(5, 6, 8)
    g.addEdge(5, 9, 7)
    g.addEdge(6, 7, 2)
    g.addEdge(6, 8, 10)
    g.addEdge(8, 9, 3)
    #  Display graph element
    g.printGraph()
    g.primMST()
end

main()

input

 Graph Adjacency List  
 [0] :  1  7  8 
 [1] :  0  2  8 
 [2] :  1  3  6  9 
 [3] :  2  4  9 
 [4] :  3  5 
 [5] :  4  6  9 
 [6] :  2  5  7  8 
 [7] :  0  6 
 [8] :  0  1  6  9 
 [9] :  2  3  5  8

 Minimum Spanning Tree 
 Edge (8-1)  weight : 6
 Edge (3-2)  weight : 8
 Edge (9-3)  weight : 5
 Edge (5-4)  weight : 15
 Edge (9-5)  weight : 7
 Edge (7-6)  weight : 2
 Edge (0-7)  weight : 6
 Edge (0-8)  weight : 4
 Edge (8-9)  weight : 3
 Total minimum weight : 56
import scala.collection.mutable._;
/*
    Scala program for
    Prim's algorithm using adjacency list
*/
class Edge(
    // Source node
    var u: Int,
        // Destination node
        var v: Int,
            // Edge weight
            var weight: Int)
{}
class HeapNode(var vertex: Int,
    var key: Int)
{
    def this()
    {
        this(0,0);
    }
}
class ResultSet(var parent: Int,
    var weight: Int)
{
    def this()
    {
        this(0,0);
    }
}
class MinHeap(var capacity: Int,
    var currentSize: Int,
        var node: Array[HeapNode],
            var indexes: Array[Int])
{
    def this(capacity: Int)
    {
        this(capacity,0,Array.fill[HeapNode](capacity + 1)(null),Array.fill[Int](capacity)(0));
        node(0) = new HeapNode();
        node(0).key = Int.MinValue;
        node(0).vertex = -1;
        
    }
    def swap(a: Int, b: Int): Unit = {
        var temp: HeapNode = node(a);
        node(a) = node(b);
        node(b) = temp;
    }
    def isEmpty(): Boolean = {
        return currentSize == 0;
    }
    def heapSize(): Int = {
        return currentSize;
    }
    def bubbleUp(pos: Int): Unit = {
        var parentIdx: Int = pos / 2;
        var currentIdx: Int = pos;
        while (currentIdx > 0 && node(parentIdx).key > node(currentIdx).key)
        {
            var currentNode: HeapNode = node(currentIdx);
            var parentNode: HeapNode = node(parentIdx);
            indexes(currentNode.vertex) = parentIdx;
            indexes(parentNode.vertex) = currentIdx;
            swap(currentIdx, parentIdx);
            currentIdx = parentIdx;
            parentIdx = parentIdx / 2;
        }
    }
    def insert(x: HeapNode): Unit = {
        currentSize += 1;
        var idx: Int = currentSize;
        node(idx) = x;
        indexes(x.vertex) = idx;
        bubbleUp(idx);
    }
    def extractMin(): HeapNode = {
        var min: HeapNode = node(1);
        var lastNode: HeapNode = node(currentSize);
        indexes(lastNode.vertex) = 1;
        node(1) = lastNode;
        node(currentSize) = null;
        sinkDown(1);
        currentSize -= 1;
        return min;
    }
    def sinkDown(k: Int): Unit = {
        var smallest: Int = k;
        // left child
        var leftChild: Int = 2 * k;
        // right child
        var rightChild: Int = 2 * k + 1;
        if (leftChild < heapSize() && node(smallest).key > node(leftChild).key)
        {
            smallest = leftChild;
        }
        if (rightChild < heapSize() && node(smallest).key > node(rightChild).key)
        {
            smallest = rightChild;
        }
        if (smallest != k)
        {
            var smallestNode: HeapNode = node(smallest);
            var kNode: HeapNode = node(k);
            indexes(smallestNode.vertex) = k;
            indexes(kNode.vertex) = smallest;
            swap(k, smallest);
            sinkDown(smallest);
        }
    }
}
class Graph(var vertices: Int,
    var adjacencylist: ArrayBuffer[ArrayBuffer[Edge]])
{
    def this(vertices: Int)
    {
        this(vertices,new ArrayBuffer[ArrayBuffer[Edge]](vertices));
        var i: Int = 0;
        while (i < this.vertices)
        {
            this.adjacencylist += new ArrayBuffer[Edge]();
            i += 1;
        }
    }
    def addEdge(u: Int, v: Int, weight: Int): Unit = {
        adjacencylist(u) += new Edge(u, v, weight);
        if (u == v)
        {
            // self loop
            return;
        }
        adjacencylist(v) += new Edge(v, u, weight);
    }
    def decreaseKey(minHeap: MinHeap, newKey: Int, vertex: Int): Unit = {
        var index: Int = minHeap.indexes(vertex);
        var node: HeapNode = minHeap.node(index);
        node.key = newKey;
        minHeap.bubbleUp(index);
    }
    def primMST(): Unit = {
        var inHeap: Array[Boolean] = Array.fill[Boolean](this.vertices)(false);
        var resultSet: Array[ResultSet] = Array.fill[ResultSet](this.vertices)(null);
        var key: Array[Int] = Array.fill[Int](this.vertices)(0);
        var heapNodes: Array[HeapNode] = Array.fill[HeapNode](this.vertices)(null);
        var i: Int = 0;
        // Set default value of heap nodes resultset and keys
        while (i < this.vertices)
        {
            heapNodes(i) = new HeapNode();
            heapNodes(i).vertex = i;
            heapNodes(i).key = Int.MaxValue;
            resultSet(i) = new ResultSet();
            resultSet(i).parent = -1;
            inHeap(i) = true;
            key(i) = Int.MaxValue;
            i += 1;
        }
        heapNodes(0).key = 0;
        var minHeap: MinHeap = new MinHeap(this.vertices);
        var j: Int = 0;
        while (j < this.vertices)
        {
            minHeap.insert(heapNodes(j));
            j += 1;
        }
        i = 0;
        while (minHeap.isEmpty() == false)
        {
            var extractedNode: HeapNode = minHeap.extractMin();
            var extractedVertex: Int = extractedNode.vertex;
            inHeap(extractedVertex) = false;
            while (i < adjacencylist(extractedVertex).size)
            {
                var edge: Edge = adjacencylist(extractedVertex)(i);
                if (inHeap(edge.v))
                {
                    var v: Int = edge.v;
                    var w: Int = edge.weight;
                    if (key(v) > w)
                    {
                        key(v) = w;
                        decreaseKey(minHeap, w, v);
                        resultSet(v).parent = extractedVertex;
                        resultSet(v).weight = w;
                    }
                }
                i += 1;
            }
            i = 0;
        }
        var result: Int = 0;
        print("\n\n Minimum Spanning Tree \n");
        var node: Int = 1;
        while (node < this.vertices)
        {
            println(" Edge (" + resultSet(node).parent + "-" + node + ")  weight : " + resultSet(node).weight);
            result += resultSet(node).weight;
            node += 1;
        }
        // Display calculated result
        println(" Total minimum weight : " + result);
    }
    // Display graph nodes and edges
    def printGraph(): Unit = {
        print("\n Graph Adjacency List ");
        var i: Int = 0;
        while (i < this.vertices)
        {
            print(" \n [" + i + "] :");
            var j: Int = 0;
            // iterate edges of i node
            while (j < this.adjacencylist(i).size)
            {
                print("  " + this.adjacencylist(i)(j).v);
                j += 1;
            }
            i += 1;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var g: Graph = new Graph(10);
        g.addEdge(0, 1, 7);
        g.addEdge(0, 7, 6);
        g.addEdge(0, 8, 4);
        g.addEdge(1, 2, 9);
        g.addEdge(1, 8, 6);
        g.addEdge(2, 3, 8);
        g.addEdge(2, 6, 12);
        g.addEdge(2, 9, 14);
        g.addEdge(3, 4, 16);
        g.addEdge(3, 9, 5);
        g.addEdge(4, 5, 15);
        g.addEdge(5, 6, 8);
        g.addEdge(5, 9, 7);
        g.addEdge(6, 7, 2);
        g.addEdge(6, 8, 10);
        g.addEdge(8, 9, 3);
        // Display graph element
        g.printGraph();
        g.primMST();
    }
}

input

 Graph Adjacency List
 [0] :  1  7  8
 [1] :  0  2  8
 [2] :  1  3  6  9
 [3] :  2  4  9
 [4] :  3  5
 [5] :  4  6  9
 [6] :  2  5  7  8
 [7] :  0  6
 [8] :  0  1  6  9
 [9] :  2  3  5  8

 Minimum Spanning Tree
 Edge (8-1)  weight : 6
 Edge (3-2)  weight : 8
 Edge (9-3)  weight : 5
 Edge (5-4)  weight : 15
 Edge (9-5)  weight : 7
 Edge (7-6)  weight : 2
 Edge (0-7)  weight : 6
 Edge (0-8)  weight : 4
 Edge (8-9)  weight : 3
 Total minimum weight : 56
import Foundation;
/*
    Swift 4 program for
    Prim's algorithm using adjacency list
*/
class Edge
{
    // Source node
    var u: Int;
    // Destination node
    var v: Int;
    // Edge weight
    var weight: Int;
    init(_ u: Int, _ v: Int, _ weight: Int)
    {
        self.u = u;
        self.v = v;
        self.weight = weight;
    }
}
class HeapNode
{
    var vertex: Int;
    var key: Int;
    init()
    {
        self.vertex = 0;
        self.key = 0;
    }
}
class ResultSet
{
    var parent: Int;
    var weight: Int;
    init()
    {
        self.parent = 0;
        self.weight = 0;
    }
}
class MinHeap
{
    var capacity: Int;
    var currentSize: Int;
    var node: [HeapNode? ];
    var indexes: [Int];
    init(_ capacity: Int)
    {
        self.capacity = capacity;
        self.node = Array(repeating: nil, count: capacity + 1);
        self.indexes = Array(repeating: 0, count: capacity);
        self.node[0] = HeapNode();
        self.node[0]!.key = Int.min;
        self.node[0]!.vertex = -1;
        self.currentSize = 0;
    }
    func swap(_ a: Int, _ b: Int)
    {
        let temp: HeapNode? = self.node[a];
        self.node[a] = self.node[b];
        self.node[b] = temp;
    }
    func isEmpty() -> Bool
    {
        return self.currentSize == 0;
    }
    func heapSize() -> Int
    {
        return self.currentSize;
    }
    func bubbleUp(_ pos: Int)
    {
        var parentIdx: Int = pos / 2;
        var currentIdx: Int = pos;
        while (currentIdx > 0 
               && self.node[parentIdx]!.key > self.node[currentIdx]!.key)
        {
            let currentNode: HeapNode? = self.node[currentIdx];
            let parentNode: HeapNode? = self.node[parentIdx];
            self.indexes[currentNode!.vertex] = parentIdx;
            self.indexes[parentNode!.vertex] = currentIdx;
            self.swap(currentIdx, parentIdx);
            currentIdx = parentIdx;
            parentIdx = parentIdx / 2;
        }
    }
    func insert(_ x: HeapNode? )
    {
        self.currentSize += 1;
        let idx: Int = self.currentSize;
        self.node[idx] = x;
        self.indexes[x!.vertex] = idx;
        self.bubbleUp(idx);
    }
    func extractMin() -> HeapNode?
    {
        let min: HeapNode? = self.node[1];
        let lastNode: HeapNode? = self.node[self.currentSize];
        self.indexes[lastNode!.vertex] = 1;
        self.node[1] = lastNode;
        self.node[self.currentSize] = nil;
        self.sinkDown(1);
        self.currentSize -= 1;
        return min;
    }
    func sinkDown(_ k: Int)
    {
        var smallest: Int = k;
        // left child
        let leftChild: Int = 2 * k;
        // right child
        let rightChild: Int = 2 * k + 1;
        if (leftChild < self.heapSize() 
            && self.node[smallest]!.key > self.node[leftChild]!.key)
        {
            smallest = leftChild;
        }
        if (rightChild < self.heapSize() 
            && self.node[smallest]!.key > self.node[rightChild]!.key)
        {
            smallest = rightChild;
        }
        if (smallest  != k)
        {
            let smallestNode: HeapNode? = self.node[smallest];
            let kNode: HeapNode? = self.node[k];
            self.indexes[smallestNode!.vertex] = k;
            self.indexes[kNode!.vertex] = smallest;
            self.swap(k, smallest);
            self.sinkDown(smallest);
        }
    }
}
class Graph
{
    var vertices: Int;
    var adjacencylist: [
        [Edge?]
    ];
    init(_ vertices: Int)
    {
        self.vertices = vertices;
        self.adjacencylist = [[Edge?]]();
        var i: Int = 0;
        while (i < self.vertices)
        {
            self.adjacencylist.append([Edge?]());
            i += 1;
        }
    }
    func addEdge(_ u: Int, _ v: Int, _ weight: Int)
    {
        self.adjacencylist[u].append(Edge(u, v, weight));
        if (u == v)
        {
            // self loop
            return;
        }
        self.adjacencylist[v].append(Edge(v, u, weight));
    }
    func decreaseKey(_ minHeap: MinHeap? , _ newKey : Int, _ vertex: Int)
    {
        let index: Int = minHeap!.indexes[vertex];
        let node: HeapNode? = minHeap!.node[index];
        node!.key = newKey;
        minHeap!.bubbleUp(index);
    }
    func primMST()
    {
        var inHeap: [Bool] = 
                        Array(repeating: false, count: self.vertices);
        var resultSet: [ResultSet? ] = 
                        Array(repeating: nil, count: self.vertices);
        var key: [Int] = 
                        Array(repeating: 0, count: self.vertices);
        var heapNodes: [HeapNode? ] = 
                        Array(repeating: nil, count: self.vertices);
        var i: Int = 0;
        // Set default value of heap nodes resultset and keys
        while (i < self.vertices)
        {
            heapNodes[i] = HeapNode();
            heapNodes[i]!.vertex = i;
            heapNodes[i]!.key = Int.max;
            resultSet[i] = ResultSet();
            resultSet[i]!.parent = -1;
            inHeap[i] = true;
            key[i] = Int.max;
            i += 1;
        }
        heapNodes[0]!.key = 0;
        let minHeap: MinHeap? = MinHeap(self.vertices);
        var j: Int = 0;
        while (j < self.vertices)
        {
            minHeap!.insert(heapNodes[j]);
            j += 1;
        }
        i = 0;
        while (minHeap!.isEmpty() == false)
        {
            let extractedNode: HeapNode? = minHeap!.extractMin();
            let extractedVertex: Int = extractedNode!.vertex;
            inHeap[extractedVertex] = false;
            while (i < self.adjacencylist[extractedVertex].count)
            {
                let edge: Edge? = self.adjacencylist[extractedVertex][i];
                if (inHeap[edge!.v])
                {
                    let v: Int = edge!.v;
                    let w: Int = edge!.weight;
                    if (key[v] > w)
                    {
                        key[v] = w;
                        self.decreaseKey(minHeap, w, v);
                        resultSet[v]!.parent = extractedVertex;
                        resultSet[v]!.weight = w;
                    }
                }
                i += 1;
            }
            i = 0;
        }
        var result: Int = 0;
        print("\n\n Minimum Spanning Tree ");
        var node: Int = 1;
        while (node < self.vertices)
        {
            print(" Edge (", resultSet[node]!.parent ,"-", 
                  node ,")  weight : ", resultSet[node]!.weight);
            result += resultSet[node]!.weight;
            node += 1;
        }
        // Display calculated result
        print(" Total minimum weight : ", result);
    }
    // Display graph nodes and edges
    func printGraph()
    {
        print("\n Graph Adjacency List ", terminator: "");
        var i: Int = 0;
        while (i < self.vertices)
        {
            print(" \n [", i ,"] :", terminator: "");
            var j: Int = 0;
            // iterate edges of i node
            while (j < self.adjacencylist[i].count)
            {
                print("  ", self.adjacencylist[i][j]!.v, terminator: "");
                j += 1;
            }
            i += 1;
        }
    }
}
func main()
{
    let g: Graph = Graph(10);
    g.addEdge(0, 1, 7);
    g.addEdge(0, 7, 6);
    g.addEdge(0, 8, 4);
    g.addEdge(1, 2, 9);
    g.addEdge(1, 8, 6);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 6, 12);
    g.addEdge(2, 9, 14);
    g.addEdge(3, 4, 16);
    g.addEdge(3, 9, 5);
    g.addEdge(4, 5, 15);
    g.addEdge(5, 6, 8);
    g.addEdge(5, 9, 7);
    g.addEdge(6, 7, 2);
    g.addEdge(6, 8, 10);
    g.addEdge(8, 9, 3);
    // Display graph element
    g.printGraph();
    g.primMST();
}
main();

input

 Graph Adjacency List
 [ 0 ] :   1   7   8
 [ 1 ] :   0   2   8
 [ 2 ] :   1   3   6   9
 [ 3 ] :   2   4   9
 [ 4 ] :   3   5
 [ 5 ] :   4   6   9
 [ 6 ] :   2   5   7   8
 [ 7 ] :   0   6
 [ 8 ] :   0   1   6   9
 [ 9 ] :   2   3   5   8

 Minimum Spanning Tree
 Edge ( 8 - 1 )  weight :  6
 Edge ( 3 - 2 )  weight :  8
 Edge ( 9 - 3 )  weight :  5
 Edge ( 5 - 4 )  weight :  15
 Edge ( 9 - 5 )  weight :  7
 Edge ( 7 - 6 )  weight :  2
 Edge ( 0 - 7 )  weight :  6
 Edge ( 0 - 8 )  weight :  4
 Edge ( 8 - 9 )  weight :  3
 Total minimum weight :  56
/*
    Kotlin program for
    Prim's algorithm using adjacency list
*/
class Edge
{
    // Source node
    var u: Int;
    // Destination node
    var v: Int;
    // Edge weight
    var weight: Int;
    constructor(u: Int, v: Int, weight: Int)
    {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }
}
class HeapNode
{
    var vertex: Int;
    var key: Int;
    constructor()
    {
        this.vertex = 0;
        this.key = 0;
    }
}
class ResultSet
{
    var parent: Int;
    var weight: Int;
    constructor()
    {
        this.parent = 0;
        this.weight = 0;
    }
}
class MinHeap
{
    var capacity: Int;
    var currentSize: Int;
    var node: Array < HeapNode ? > ;
    var indexes: Array < Int > ;
    constructor(capacity: Int)
    {
        this.capacity = capacity;
        this.node = Array(capacity + 1)
        {
            null
        };
        this.indexes = Array(capacity)
        {
            0
        };
        this.node[0] = HeapNode();
        this.node[0]!!.key = Int.MIN_VALUE;
        this.node[0]!!.vertex = -1;
        this.currentSize = 0;
    }
    fun swap(a: Int, b: Int): Unit
    {
        val temp: HeapNode? = this.node[a];
        this.node[a] = this.node[b];
        this.node[b] = temp;
    }
    fun isEmpty(): Boolean
    {
        return this.currentSize == 0;
    }
    fun heapSize(): Int
    {
        return this.currentSize;
    }
    fun bubbleUp(pos: Int): Unit
    {
        var parentIdx: Int = pos / 2;
        var currentIdx: Int = pos;
        while (currentIdx > 0 
               && this.node[parentIdx]!!.key > this.node[currentIdx]!!.key)
        {
            val currentNode: HeapNode? = this.node[currentIdx];
            val parentNode: HeapNode? = this.node[parentIdx];
            this.indexes[currentNode!!.vertex] = parentIdx;
            this.indexes[parentNode!!.vertex] = currentIdx;
            this.swap(currentIdx, parentIdx);
            currentIdx = parentIdx;
            parentIdx = parentIdx / 2;
        }
    }
    fun insert(x: HeapNode ? ): Unit
    {
        this.currentSize += 1;
        val idx: Int = this.currentSize;
        this.node[idx] = x;
        this.indexes[x!!.vertex] = idx;
        this.bubbleUp(idx);
    }
    fun extractMin(): HeapNode ?
    {
        val min: HeapNode? = this.node[1];
        val lastNode: HeapNode? = this.node[this.currentSize];
        this.indexes[lastNode!!.vertex] = 1;
        this.node[1] = lastNode;
        this.node[this.currentSize] = null;
        this.sinkDown(1);
        this.currentSize -= 1;
        return min;
    }
    fun sinkDown(k: Int): Unit
    {
        var smallest: Int = k;
        // left child
        val leftChild: Int = 2 * k;
        // right child
        val rightChild: Int = 2 * k + 1;
        if (leftChild < this.heapSize() && this.node[smallest]!!.key > this.node[leftChild]!!.key)
        {
            smallest = leftChild;
        }
        if (rightChild < this.heapSize() && this.node[smallest]!!.key > this.node[rightChild]!!.key)
        {
            smallest = rightChild;
        }
        if (smallest != k)
        {
            val smallestNode: HeapNode? = this.node[smallest];
            val kNode: HeapNode? = this.node[k];
            this.indexes[smallestNode!!.vertex] = k;
            this.indexes[kNode!!.vertex] = smallest;
            this.swap(k, smallest);
            this.sinkDown(smallest);
        }
    }
}
class Graph
{
    var vertices: Int;
    var adjacencylist: MutableList < MutableList < Edge >> ;
    constructor(vertices: Int)
    {
        this.vertices = vertices;
        this.adjacencylist = mutableListOf<MutableList<Edge>>();
        var i: Int = 0;
        while (i < this.vertices)
        {
            this.adjacencylist.add(mutableListOf<Edge>());
            i += 1;
        }
    }
    fun addEdge(u: Int, v: Int, weight: Int): Unit
    {
        this.adjacencylist[u].add(Edge(u, v, weight));
        if (u == v)
        {
            // self loop
            return;
        }
        this.adjacencylist[v].add(Edge(v, u, weight));
    }
    fun decreaseKey(minHeap: MinHeap ? , newKey : Int, vertex: Int): Unit
    {
        val index: Int = minHeap!!.indexes[vertex];
        var node: HeapNode ? = minHeap.node[index];
        node!!.key = newKey;
        minHeap.bubbleUp(index);
    }
    fun primMST(): Unit
    {
        val inHeap: Array < Boolean > = Array(this.vertices)
        {
            false
        };
        val resultSet: Array < ResultSet ? > = Array(this.vertices)
        {
            null
        };
        val key: Array < Int > = Array(this.vertices)
        {
            0
        };
        val heapNodes: Array < HeapNode ? > = Array(this.vertices)
        {
            null
        };
        var i: Int = 0;
        // Set default value of heap nodes resultset and keys
        while (i < this.vertices)
        {
            heapNodes[i] = HeapNode();
            heapNodes[i]!!.vertex = i;
            heapNodes[i]!!.key = Int.MAX_VALUE;
            resultSet[i] = ResultSet();
            resultSet[i]!!.parent = -1;
            inHeap[i] = true;
            key[i] = Int.MAX_VALUE;
            i += 1;
        }
        heapNodes[0]?.key = 0;
        val minHeap: MinHeap = MinHeap(this.vertices);
        var j: Int = 0;
        while (j < this.vertices)
        {
            minHeap.insert(heapNodes[j]);
            j += 1;
        }
        i = 0;
        while (minHeap.isEmpty() == false)
        {
            val extractedNode: HeapNode? = minHeap.extractMin();
            val extractedVertex: Int = extractedNode!!.vertex;
            inHeap[extractedVertex] = false;
            while (i < this.adjacencylist[extractedVertex].size)
            {
                val edge: Edge? = this.adjacencylist[extractedVertex][i];
                if (inHeap[edge!!.v])
                {
                    val v: Int = edge.v;
                    val w: Int = edge.weight;
                    if (key[v] > w)
                    {
                        key[v] = w;
                        this.decreaseKey(minHeap, w, v);
                        resultSet[v]!!.parent = extractedVertex;
                        resultSet[v]!!.weight = w;
                    }
                }
                i += 1;
            }
            i = 0;
        }
        var result: Int = 0;
        print("\n\n Minimum Spanning Tree \n");
        var node: Int = 1;
        while (node < this.vertices)
        {
            println(" Edge (" + resultSet[node]!!.parent + "-" + node + ")  weight : " + resultSet[node]!!.weight);
            result += resultSet[node]!!.weight;
            node += 1;
        }
        // Display calculated result
        println(" Total minimum weight : " + result);
    }
    // Display graph nodes and edges
    fun printGraph(): Unit
    {
        print("\n Graph Adjacency List ");
        var i: Int = 0;
        while (i < this.vertices)
        {
            print(" \n [" + i + "] :");
            var j: Int = 0;
            // iterate edges of i node
            while (j < this.adjacencylist[i].size)
            {
                print("  " + this.adjacencylist[i][j].v);
                j += 1;
            }
            i += 1;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val g: Graph = Graph(10);
    g.addEdge(0, 1, 7);
    g.addEdge(0, 7, 6);
    g.addEdge(0, 8, 4);
    g.addEdge(1, 2, 9);
    g.addEdge(1, 8, 6);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 6, 12);
    g.addEdge(2, 9, 14);
    g.addEdge(3, 4, 16);
    g.addEdge(3, 9, 5);
    g.addEdge(4, 5, 15);
    g.addEdge(5, 6, 8);
    g.addEdge(5, 9, 7);
    g.addEdge(6, 7, 2);
    g.addEdge(6, 8, 10);
    g.addEdge(8, 9, 3);
    // Display graph element
    g.printGraph();
    g.primMST();
}

input

 Graph Adjacency List
 [0] :  1  7  8
 [1] :  0  2  8
 [2] :  1  3  6  9
 [3] :  2  4  9
 [4] :  3  5
 [5] :  4  6  9
 [6] :  2  5  7  8
 [7] :  0  6
 [8] :  0  1  6  9
 [9] :  2  3  5  8

 Minimum Spanning Tree
 Edge (8-1)  weight : 6
 Edge (3-2)  weight : 8
 Edge (9-3)  weight : 5
 Edge (5-4)  weight : 15
 Edge (9-5)  weight : 7
 Edge (7-6)  weight : 2
 Edge (0-7)  weight : 6
 Edge (0-8)  weight : 4
 Edge (8-9)  weight : 3
 Total minimum weight : 56
package main
import "math"
import "fmt"
/*
    Go program for
    Prim's algorithm using adjacency list
*/
type Edge struct {
        
    u int // Source node
    v int // Destination node
    weight int // Edge weight
    
    
}
func getEdge(u int, v int, weight int) * Edge {
    var me *Edge = &Edge {u,v,weight}
    return me
}
type HeapNode struct {
    vertex int
    key int
}
func getHeapNode() * HeapNode {
    var me *HeapNode = &HeapNode {}
    return me
}
type ResultSet struct {
    parent int
    weight int
}
func getResultSet() * ResultSet {
    var me *ResultSet = &ResultSet {}
    return me
}
type MinHeap struct {
    capacity int
    currentSize int
    node []* HeapNode
    indexes []int
}
func getMinHeap(capacity int) * MinHeap {
    var me *MinHeap = &MinHeap {}
    me.capacity = capacity
    me.node = make([]*HeapNode, capacity + 1)
    me.indexes = make([] int, capacity)
    me.node[0] = getHeapNode()
    me.node[0].key = math.MinInt64
    me.node[0].vertex = -1
    me.currentSize = 0
    return me
}
func(this MinHeap) swap(a, b int) {
    var temp * HeapNode = this.node[a]
    this.node[a] = this.node[b]
    this.node[b] = temp
}
func(this MinHeap) isEmpty() bool {
    return this.currentSize == 0
}
func(this MinHeap) heapSize() int {
    return this.currentSize
}
func(this MinHeap) bubbleUp(pos int) {
    var parentIdx int = pos / 2
    var currentIdx int = pos
    for (currentIdx > 0 && 
         this.node[parentIdx].key > this.node[currentIdx].key) {
        var currentNode * HeapNode = this.node[currentIdx]
        var parentNode * HeapNode = this.node[parentIdx]
        this.indexes[currentNode.vertex] = parentIdx
        this.indexes[parentNode.vertex] = currentIdx
        this.swap(currentIdx, parentIdx)
        currentIdx = parentIdx
        parentIdx = parentIdx / 2
    }
}
func(this *MinHeap) insert(x * HeapNode) {
    this.currentSize++
    var idx int = this.currentSize
    this.node[idx] = x
    this.indexes[x.vertex] = idx
    this.bubbleUp(idx)
}
func(this *MinHeap) extractMin() * HeapNode {
    var min * HeapNode = this.node[1]
    var lastNode * HeapNode = this.node[this.currentSize]
    this.indexes[lastNode.vertex] = 1
    this.node[1] = lastNode
    this.node[this.currentSize] = nil
    this.sinkDown(1)
    this.currentSize--
    return min
}
func(this MinHeap) sinkDown(k int) {
    var smallest int = k
    // left child
    var leftChild int = 2 * k
    // right child
    var rightChild int = 2 * k + 1
    if leftChild < this.heapSize() && 
      this.node[smallest].key > this.node[leftChild].key {
        smallest = leftChild
    }
    if rightChild < this.heapSize() && 
      this.node[smallest].key > this.node[rightChild].key {
        smallest = rightChild
    }
    if smallest != k {
        var smallestNode * HeapNode = this.node[smallest]
        var kNode * HeapNode = this.node[k]
        this.indexes[smallestNode.vertex] = k
        this.indexes[kNode.vertex] = smallest
        this.swap(k, smallest)
        this.sinkDown(smallest)
    }
}
type Graph struct {
    vertices int
    adjacencylist [][]*Edge
}
func getGraph(vertices int) * Graph {
    var me *Graph = &Graph {}
    me.vertices = vertices
    me.adjacencylist = make([][]*Edge,vertices)
    for i := 0 ; i < me.vertices ; i++ {
        me.adjacencylist = append(me.adjacencylist)
    }
    return me
}
func(this *Graph) addEdge(u, v, weight int) {
    this.adjacencylist[u] = append(this.adjacencylist[u], getEdge(u, v, weight))
    if u == v {
        // self loop
        return
    }
    this.adjacencylist[v] = append(this.adjacencylist[v], getEdge(v, u, weight))
}
func(this Graph) decreaseKey(minHeap * MinHeap, newKey int, vertex int) {
    var index int = minHeap.indexes[vertex]
    var node * HeapNode = minHeap.node[index]
    node.key = newKey
    minHeap.bubbleUp(index)
}
func(this Graph) primMST() {
    var inHeap = make([] bool, this.vertices)
    var resultSet = make([] *ResultSet, this.vertices)
    var key = make([] int, this.vertices)
    var heapNodes = make([] *HeapNode, this.vertices)
    // Set default value of heap nodes resultset and keys
    for i := 0 ; i < this.vertices ; i++ {
        heapNodes[i] = getHeapNode()
        heapNodes[i].vertex = i
        heapNodes[i].key = math.MaxInt64
        resultSet[i] = getResultSet()
        resultSet[i].parent = -1
        inHeap[i] = true
        key[i] = math.MaxInt64
    }
    heapNodes[0].key = 0
    var minHeap * MinHeap = getMinHeap(this.vertices)
    for j := 0 ; j < this.vertices ; j++ {
        minHeap.insert(heapNodes[j])
    }
    var i int = 0
    for (minHeap.isEmpty() == false) {
        var extractedNode * HeapNode = minHeap.extractMin()
        var extractedVertex int = extractedNode.vertex
        inHeap[extractedVertex] = false
        for (i < len(this.adjacencylist[extractedVertex])) {
            var edge * Edge = this.adjacencylist[extractedVertex][i]
            if inHeap[edge.v] {
                var v int = edge.v
                var w int = edge.weight
                if key[v] > w {
                    key[v] = w
                    this.decreaseKey(minHeap, w, v)
                    resultSet[v].parent = extractedVertex
                    resultSet[v].weight = w
                }
            }
            i++
        }
        i = 0
    }
    var result int = 0
    fmt.Print("\n\n Minimum Spanning Tree \n")
    for node := 1 ; node < this.vertices ; node++ {
        fmt.Println(" Edge (", 
                    resultSet[node].parent, "-", 
                    node, ")  weight : ", resultSet[node].weight)
        result += resultSet[node].weight
    }
    // Display calculated result
    fmt.Println(" Total minimum weight : ", result)
}
// Display graph nodes and edges
func(this Graph) printGraph() {
    fmt.Print("\n Graph Adjacency List ")
    for i := 0 ; i < this.vertices ; i++ {
        fmt.Print(" \n [", i, "] :")
        // iterate edges of i node
        for j := 0 ; j < len(this.adjacencylist[i]) ; j++ {
            fmt.Print("  ", this.adjacencylist[i][j].v)
        }
    }
}
func main() {
    var g * Graph = getGraph(10)
    g.addEdge(0, 1, 7)
    g.addEdge(0, 7, 6)
    g.addEdge(0, 8, 4)
    g.addEdge(1, 2, 9)
    g.addEdge(1, 8, 6)
    g.addEdge(2, 3, 8)
    g.addEdge(2, 6, 12)
    g.addEdge(2, 9, 14)
    g.addEdge(3, 4, 16)
    g.addEdge(3, 9, 5)
    g.addEdge(4, 5, 15)
    g.addEdge(5, 6, 8)
    g.addEdge(5, 9, 7)
    g.addEdge(6, 7, 2)
    g.addEdge(6, 8, 10)
    g.addEdge(8, 9, 3)
    // Display graph element
    g.printGraph()
    g.primMST()
}

Output

 Graph Adjacency List  
 [0] :  1  7  8 
 [1] :  0  2  8 
 [2] :  1  3  6  9 
 [3] :  2  4  9 
 [4] :  3  5 
 [5] :  4  6  9 
 [6] :  2  5  7  8 
 [7] :  0  6 
 [8] :  0  1  6  9 
 [9] :  2  3  5  8

 Minimum Spanning Tree 
 Edge ( 8 - 1 )  weight :  6
 Edge ( 3 - 2 )  weight :  8
 Edge ( 9 - 3 )  weight :  5
 Edge ( 5 - 4 )  weight :  15
 Edge ( 9 - 5 )  weight :  7
 Edge ( 7 - 6 )  weight :  2
 Edge ( 0 - 7 )  weight :  6
 Edge ( 0 - 8 )  weight :  4
 Edge ( 8 - 9 )  weight :  3
 Total minimum weight :  56




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment