The algorithm

PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
boolean[] inTree = new boolean[n];
pq.offer(new int[]{0, start});
long total = 0;
while (!pq.isEmpty()) {
  int[] cur = pq.poll();
  int w = cur[0], u = cur[1];
  if (inTree[u]) continue;
  inTree[u] = true; total += w;
  for (int[] edge : graph[u]) {
    int v = edge[0], ew = edge[1];
    if (!inTree[v]) pq.offer(new int[]{ew, v});
  }
}
Advertisement

Complexity

O((V + E) log V) with binary heap. O(E + V log V) with Fibonacci heap.

Advertisement

vs Kruskal

Prim better for dense graphs (higher E/V ratio). Kruskal better for sparse. Both O(E log E) essentially.

Dense variant

Adjacency matrix + O(V²) Prim without PQ. Beats O(E log V) when E ≈ V².