Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Friday, June 12

    Prims Algorithm Code

    Updated: Algorithms No Comments4 Mins Readdevangini123By

    Prim’s Algorithm

    Initial Priority Queue:

    Code

    class MinPriorityQueue {
    constructor(config) {
        this.priority = config.priority;
        this.heap = [];
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    enqueue(element) {
        this.heap.push(element);
        this._bubbleUp();
    }

    dequeue() {
        if (this.isEmpty()) return null;

        const top = this.heap[0];
        const last = this.heap.pop();

        if (!this.isEmpty()) {
            this.heap[0] = last;
            this._bubbleDown();
        }

        return { element: top };
    }

    _bubbleUp() {
        let i = this.heap.length - 1;

        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);

            if (this.priority(this.heap[i]) < this.priority(this.heap[parent])) {
                [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
                i = parent;
            } else {
                break;
            }
        }
    }

    _bubbleDown() {
        let i = 0;

        while (true) {
            let left = 2 * i + 1;
            let right = 2 * i + 2;
            let smallest = i;

            if (left < this.heap.length &&
                this.priority(this.heap[left]) < this.priority(this.heap[smallest])) {
                smallest = left;
            }

            if (right < this.heap.length &&
                this.priority(this.heap[right]) < this.priority(this.heap[smallest])) {
                smallest = right;
            }

            if (smallest !== i) {
                [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
                i = smallest;
            } else {
                break;
            }
        }
    }
}

function primMST(n, graph) {
    let visited = new Array(n).fill(false);
    let pq = new MinPriorityQueue({ priority: (x) => x[0] });

    pq.enqueue([0, 0]);

    let edgesUsed = 0;
    let mstCost = 0;

    while (!pq.isEmpty() && edgesUsed < n) {
        let [weight, node] = pq.dequeue().element;

        if (visited[node]) continue;

        visited[node] = true;
        edgesUsed++;
        mstCost += weight;

        for (let [edge, edgeWt] of graph[node]) {
            if (!visited[edge]) {
                pq.enqueue([edgeWt, edge]);
            }
        }
    }
    return mstCost;
}

const graph = [
    [[1, 4], [2, 2], [3, 5]],
    [[0, 4], [3, 1]],
    [[0, 2], [3, 3]],
    [[1, 1], [2, 3]]
];

console.log(primMST(4, graph));

    import heapq

def primMST(n, graph):
    visited = [False] * n
    pq = []

    heapq.heappush(pq, (0, 0))  # (weight, node)

    mst_cost = 0
    edges_used = 0

    while pq and edges_used < n:
        weight, node = heapq.heappop(pq)

        if visited[node]:
            continue

        visited[node] = True
        mst_cost += weight
        edges_used += 1

        for edge, edge_wt in graph[node]:
            if not visited[edge]:
                heapq.heappush(pq, (edge_wt, edge))

    return mst_cost


graph = [
    [(1, 4), (2, 2), (3, 5)],
    [(0, 4), (3, 1)],
    [(0, 2), (3, 3)],
    [(1, 1), (2, 3)]
]

print(primMST(4, graph))

    
    import java.util.*;

class Pair {
    int weight, node;

    Pair(int w, int n) {
        weight = w;
        node = n;
    }
}

public class PrimMST {

    public static int primMST(int n, List> graph) {
        boolean[] visited = new boolean[n];

        PriorityQueue pq = new PriorityQueue<>(
                (a, b) -> a.weight - b.weight
        );

        pq.add(new Pair(0, 0));
        int mstCost = 0, edgesUsed = 0;

        while (!pq.isEmpty() && edgesUsed < n) {
            Pair curr = pq.poll();

            if (visited[curr.node]) continue;

            visited[curr.node] = true;
            mstCost += curr.weight;
            edgesUsed++;

            for (Pair p : graph.get(curr.node)) {
                if (!visited[p.node]) {
                    pq.add(new Pair(p.weight, p.node));
                }
            }
        }
        return mstCost;
    }

    public static void main(String[] args) {
        List> graph = new ArrayList<>();

        for (int i = 0; i < 4; i++) graph.add(new ArrayList<>());

        graph.get(0).add(new Pair(4, 1));
        graph.get(0).add(new Pair(2, 2));
        graph.get(0).add(new Pair(5, 3));

        graph.get(1).add(new Pair(4, 0));
        graph.get(1).add(new Pair(1, 3));

        graph.get(2).add(new Pair(2, 0));
        graph.get(2).add(new Pair(3, 3));

        graph.get(3).add(new Pair(1, 1));
        graph.get(3).add(new Pair(3, 2));

        System.out.println(primMST(4, graph));
    }
}
    
    #include <bits/stdc++.h>
using namespace std;

int primMST(int n, vector>> &graph) {
    vector visited(n, false);
    priority_queue, vector>, greater<>> pq;

    pq.push({0, 0});
    int mstCost = 0;

    while (!pq.empty()) {
        auto [weight, node] = pq.top();
        pq.pop();

        if (visited[node]) continue;

        visited[node] = true;
        mstCost += weight;

        for (auto &[edge, edgeWt] : graph[node]) {
            if (!visited[edge]) {
                pq.push({edgeWt, edge});
            }
        }
    }
    return mstCost;
}

int main() {
    vector>> graph = {
        {{1,4},{2,2},{3,5}},
        {{0,4},{3,1}},
        {{0,2},{3,3}},
        {{1,1},{2,3}}
    };

    cout << primMST(4, graph);
}
  
    #include <stdio.h>
#include <limits.h>

#define V 4

int minKey(int key[], int mstSet[]) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            minIndex = v;
        }
    }
    return minIndex;
}

int primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    int mstSet[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = 0;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = 1;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    int cost = 0;
    for (int i = 1; i < V; i++)
        cost += graph[i][parent[i]];

    return cost;
}

int main() {
    int graph[V][V] = {
        {0, 4, 2, 5},
        {4, 0, 0, 1},
        {2, 0, 0, 3},
        {5, 1, 3, 0}
    };

    printf("%d\n", primMST(graph));
    return 0;
}


    using System;
using System.Collections.Generic;

class PrimMST
{
    public static int Prim(int n, List> graph)
    {
        bool[] visited = new bool[n];
        var pq = new PriorityQueue<(int weight, int node), int>();

        pq.Enqueue((0, 0), 0);
        int mstCost = 0;

        while (pq.Count > 0)
        {
            var (weight, node) = pq.Dequeue();

            if (visited[node]) continue;

            visited[node] = true;
            mstCost += weight;

            foreach (var (edge, edgeWt) in graph[node])
            {
                if (!visited[edge])
                {
                    pq.Enqueue((edgeWt, edge), edgeWt);
                }
            }
        }
        return mstCost;
    }

    static void Main()
    {
        var graph = new List> {
            new() { (1,4), (2,2), (3,5) },
            new() { (0,4), (3,1) },
            new() { (0,2), (3,3) },
            new() { (1,1), (2,3) }
        };

        Console.WriteLine(Prim(4, graph));
    }
}

    Time Complexity

    O((V + E) log V)

    Space Complexity

    O(V + E)

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us