Prim's Algorithm

#include <limits.h>
#include <stdbool.h>
#define V 5

int min_key(int key[], bool in_mst[], int n) {
    int min = INT_MAX, min_idx = -1;
    for (int v = 0; v < n; v++)
        if (!in_mst[v] && key[v] < min) { min = key[v]; min_idx = v; }
    return min_idx;
}

int prim(int graph[V][V]) {
    int parent[V], key[V]; bool in_mst[V];
    for (int i = 0; i < V; i++) { key[i] = INT_MAX; in_mst[i] = false; }
    key[0] = 0; parent[0] = -1;
    for (int count = 0; count < V - 1; count++) {
        int u = min_key(key, in_mst, V);
        in_mst[u] = true;
        for (int v = 0; v < V; v++)
            if (graph[u][v] && !in_mst[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
    }
    int total = 0;
    for (int i = 1; i < V; i++) total += key[i];
    return total;
}

#include <vector>
#include <queue>
#include <limits>
using pii = std::pair<int,int>;

int prim(const std::vector<std::vector<pii>>& adj) {
    int n = adj.size();
    std::vector<int> key(n, INT_MAX);
    std::vector<bool> in_mst(n, false);
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
    key[0] = 0;
    pq.push({0, 0});
    int mst_weight = 0;
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (in_mst[u]) continue;
        in_mst[u] = true;
        mst_weight += w;
        for (auto [edge_w, v] : adj[u])
            if (!in_mst[v] && edge_w < key[v]) {
                key[v] = edge_w;
                pq.push({key[v], v});
            }
    }
    return mst_weight;
}

import java.util.*;

public static int prim(List<List<int[]>> adj) {
    int n = adj.size();
    int[] key = new int[n];
    boolean[] inMST = new boolean[n];
    Arrays.fill(key, Integer.MAX_VALUE);
    key[0] = 0;
    // {weight, node}
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, 0});
    int mstWeight = 0;
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int w = top[0], u = top[1];
        if (inMST[u]) continue;
        inMST[u] = true;
        mstWeight += w;
        for (int[] edge : adj.get(u)) {
            int v = edge[0], ew = edge[1];
            if (!inMST[v] && ew < key[v]) {
                key[v] = ew;
                pq.offer(new int[]{key[v], v});
            }
        }
    }
    return mstWeight;
}

import heapq

def prim(adj: list[list[tuple[int,int]]]) -> int:
    n = len(adj)
    key    = [float('inf')] * n
    in_mst = [False] * n
    key[0] = 0
    heap = [(0, 0)]   # (weight, node)
    mst_weight = 0
    while heap:
        w, u = heapq.heappop(heap)
        if in_mst[u]:
            continue
        in_mst[u] = True
        mst_weight += w
        for v, edge_w in adj[u]:
            if not in_mst[v] and edge_w < key[v]:
                key[v] = edge_w
                heapq.heappush(heap, (key[v], v))
    return mst_weight

function prim(adj) {
  const n     = adj.length;
  const key   = new Array(n).fill(Infinity);
  const inMST = new Array(n).fill(false);
  key[0] = 0;
  const heap = new MinHeap(); // [weight, node]
  heap.push([0, 0]);
  let mstWeight = 0;
  while (!heap.isEmpty()) {
    const [w, u] = heap.pop();
    if (inMST[u]) continue;
    inMST[u]   = true;
    mstWeight += w;
    for (const [v, ew] of adj[u]) {
      if (!inMST[v] && ew < key[v]) {
        key[v] = ew;
        heap.push([key[v], v]);
      }
    }
  }
  return mstWeight;
}