# How Kruskal's and Prim's Algorithms Differ for MST: A Code-Based Comparison

> Compare Kruskal's and Prim's MST algorithms side-by-side. Understand their code-based differences in edge sorting, cycle avoidance, and time complexity for finding minimum spanning trees.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: deep-dive
- Published: 2026-02-24

---

**Kruskal's algorithm sorts all edges globally and uses a disjoint-set (union-find) structure to avoid cycles, while Prim's algorithm grows a single tree from an arbitrary start vertex using a priority queue to select the cheapest frontier edge, resulting in O(E log E) versus O(E log V) time complexity respectively.**

Both Kruskal's and Prim's algorithms solve the **minimum spanning tree (MST)** problem for undirected weighted graphs, yet they employ fundamentally different strategies for edge selection and cycle prevention. In the **trekhleb/javascript-algorithms** repository, these implementations demonstrate distinct architectural approaches: Kruskal's relies on global edge sorting and disjoint-set operations in [`src/algorithms/graph/kruskal/kruskal.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/kruskal/kruskal.js), while Prim's utilizes local frontier expansion with a priority queue in [`src/algorithms/graph/prim/prim.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/prim/prim.js).

## Core Algorithmic Differences

### Kruskal's Approach: Global Edge Sorting

Kruskal's algorithm treats the MST construction as a **forest merging process**. It begins by sorting all edges in the graph by weight in ascending order using `QuickSort` from [`src/algorithms/sorting/quick-sort/QuickSort.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/sorting/quick-sort/QuickSort.js). The algorithm then iterates through this sorted list, adding an edge to the MST only if it connects two previously disconnected components.

The cycle detection relies on the `DisjointSet` data structure from [`src/data-structures/disjoint-set/DisjointSet.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/disjoint-set/DisjointSet.js). Before adding an edge, the algorithm checks if the two vertices belong to the same set using the `find` operation. If they do, the edge would create a cycle and is skipped; otherwise, the sets are merged using the `union` operation.

### Prim's Approach: Local Tree Expansion

Prim's algorithm takes a **vertex-centric growth strategy**. It starts from an arbitrary vertex and maintains a single connected tree throughout execution. At each step, the algorithm examines all edges connecting the current tree to vertices outside it—the "frontier"—and selects the minimum-weight edge to bring a new vertex into the tree.

This frontier management requires a `PriorityQueue` from [`src/data-structures/priority-queue/PriorityQueue.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/priority-queue/PriorityQueue.js). The priority queue stores candidate edges keyed by weight, allowing the algorithm to efficiently retrieve the cheapest frontier edge in O(log V) time. A simple map tracks visited vertices to prevent cycles.

## Data Structures and Implementation

### Disjoint Sets and Sorting in Kruskal's

The implementation in [`src/algorithms/graph/kruskal/kruskal.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/kruskal/kruskal.js) demonstrates the algorithm's reliance on preprocessing:

1. **Edge extraction**: The algorithm first calls `graph.getAllEdges()` to retrieve every edge in the graph.
2. **Sorting**: Edges are sorted by weight using `QuickSort.sort(edges, (a, b) => a.weight - b.weight)`.
3. **Union-find operations**: For each edge, `disjointSet.find(startVertex)` and `disjointSet.find(endVertex)` determine connectivity. If the roots differ, `disjointSet.union(startVertex, endVertex)` merges the sets and the edge is added to the MST.

This approach requires O(E log E) time primarily for the sorting step, with nearly linear union-find operations.

### Priority Queues in Prim's

The [`src/algorithms/graph/prim/prim.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/prim/prim.js) implementation showcases the greedy frontier approach:

1. **Initialization**: The algorithm selects an arbitrary start vertex and marks it as visited.
2. **Priority queue seeding**: All edges from the start vertex are added to the priority queue with their weights as priorities.
3. **Greedy expansion**: While the queue is not empty, the algorithm extracts the minimum edge. If the edge leads to an unvisited vertex, that vertex is marked visited and its outgoing edges are enqueued.

The priority queue operations dominate the runtime, resulting in O(E log V) complexity with a binary heap implementation.

## Time Complexity and Performance

When choosing between Kruskal's and Prim's algorithms for MST computation, consider the graph's density and edge distribution:

- **Kruskal's algorithm** runs in **O(E log E)** time. Since E ≤ V², this is equivalent to O(E log V). The algorithm performs particularly well on **sparse graphs** where E ≈ V, as the sorting overhead is minimal and union-find operations approach O(1) amortized time.

- **Prim's algorithm** achieves **O(E log V)** time with a binary heap, or **O(E + V log V)** with a Fibonacci heap. This makes it more efficient on **dense graphs** where E approaches V², as it avoids sorting all edges upfront and only processes edges relevant to the growing tree.

Both implementations in the repository validate that the input graph is undirected, throwing an error if `graph.isDirected` returns true.

## Practical Code Examples

The following example demonstrates both algorithms using the repository's `Graph` class and MST implementations:

```javascript
import Graph from './src/data-structures/graph/Graph';
import kruskal from './src/algorithms/graph/kruskal/kruskal';
import prim from './src/algorithms/graph/prim/prim';

// Create an undirected weighted graph
const graph = new Graph();

const vertexA = graph.addVertex('A');
const vertexB = graph.addVertex('B');
const vertexC = graph.addVertex('C');
const vertexD = graph.addVertex('D');

// Add weighted edges
graph.addEdge(vertexA, vertexB, 1);
graph.addEdge(vertexA, vertexC, 3);
graph.addEdge(vertexB, vertexC, 2);
graph.addEdge(vertexB, vertexD, 4);
graph.addEdge(vertexC, vertexD, 5);

// Compute MST using Kruskal's algorithm
const mstKruskal = kruskal(graph);
console.log('Kruskal MST:', mstKruskal.getAllEdges().map(e => 
  `${e.startVertex.getKey()}-${e.endVertex.getKey()}:${e.weight}`
));

// Compute MST using Prim's algorithm
const mstPrim = prim(graph);
console.log('Prim MST:', mstPrim.getAllEdges().map(e => 
  `${e.startVertex.getKey()}-${e.endVertex.getKey()}:${e.weight}`
));

```

Both algorithms output the same MST edges (`A-B:1`, `B-C:2`, `B-D:4`), but achieve this through different internal mechanics. Kruskal's processes edges in global sorted order using the `DisjointSet` from [`src/data-structures/disjoint-set/DisjointSet.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/disjoint-set/DisjointSet.js), while Prim's uses the `PriorityQueue` from [`src/data-structures/priority-queue/PriorityQueue.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/priority-queue/PriorityQueue.js) to manage the frontier.

## Summary

- **Kruskal's algorithm** sorts all edges globally and uses a **disjoint-set (union-find)** structure to detect cycles, running in **O(E log E)** time and excelling on sparse graphs.

- **Prim's algorithm** grows a single tree from an arbitrary start vertex using a **priority queue** to select the cheapest frontier edge, running in **O(E log V)** time and performing better on dense graphs.

- Both implementations in `trekhleb/javascript-algorithms` validate undirected input graphs and return new `Graph` instances containing only MST edges.

- The choice between algorithms depends on graph density: use Kruskal's when **E ≈ V** (sparse) and Prim's when **E approaches V²** (dense).

## Frequently Asked Questions

### Which algorithm is better for finding MST, Kruskal's or Prim's?

Neither algorithm is universally superior; the optimal choice depends on graph characteristics. **Kruskal's algorithm** performs better on **sparse graphs** where the number of edges E is close to the number of vertices V, since its O(E log E) complexity is dominated by sorting. **Prim's algorithm** is preferable for **dense graphs** where E approaches V², as its O(E log V) complexity avoids the overhead of sorting all edges upfront and efficiently tracks only relevant frontier edges using a priority queue.

### Can Kruskal's and Prim's algorithms produce different MSTs?

Yes, when a graph contains **multiple edges with identical weights**, both algorithms may produce different valid minimum spanning trees with the same total weight. In `trekhleb/javascript-algorithms`, Kruskal's processes edges in globally sorted order and uses union-find to select edges, while Prim's selects the cheapest edge from the current tree's frontier. If several edges share the minimum weight at any decision point, the specific edge chosen depends on the implementation's tie-breaking behavior, resulting in different tree structures that are all equally optimal.

### Why does Kruskal's algorithm require a disjoint-set data structure?

Kruskal's algorithm processes edges in increasing weight order without tracking a single growing tree, which creates the risk of forming **cycles** when adding an edge connects two vertices already in the same connected component. The `DisjointSet` class from [`src/data-structures/disjoint-set/DisjointSet.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/disjoint-set/DisjointSet.js) provides **union-find operations** that efficiently determine whether two vertices belong to the same set (using `find`) and merge sets when a valid edge is added (using `union`). This structure achieves near-constant time per operation, enabling Kruskal's to maintain its O(E log E) complexity while ensuring the result remains acyclic.

### Does Prim's algorithm work with negative edge weights?

Yes, **Prim's algorithm correctly handles negative edge weights** because it is a greedy algorithm that selects the minimum-weight edge connecting the visited set to unvisited vertices, regardless of whether weights are positive or negative. Unlike algorithms that require non-negative weights for correctness (such as Dijkstra's shortest path algorithm), Prim's will simply include negative-weight edges in the MST if they provide the cheapest connection to a new vertex. The implementation in [`src/algorithms/graph/prim/prim.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/prim/prim.js) uses a priority queue that compares raw weight values, making it agnostic to the sign of the weight.