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

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, while Prim's utilizes local frontier expansion with a priority queue in 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. 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. 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. 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 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 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:

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, while Prim's uses the PriorityQueue from 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 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 uses a priority queue that compares raw weight values, making it agnostic to the sign of the weight.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}