Minimum Spanning Tree: MST Explained

A Minimum Spanning Tree (MST) is a spanning tree of a connected, weighted, undirected graph whose total edge weight is as small as possible.

A spanning tree connects every vertex in the graph without creating a cycle. When the graph has weighted edges, there can be multiple different spanning trees with different total costs. The minimum spanning tree is the one with the smallest possible total weight.

The two most commonly used algorithms for finding a minimum spanning tree are Kruskal's algorithm and Prim's algorithm.

What Is a Spanning Tree?

A spanning tree is a subset of the edges of a connected, undirected graph that:

• Includes every vertex.
• Connects all vertices.
• Contains no cycles.
• Contains exactly V - 1 edges for V vertices.

Consider a graph with four vertices:

A ----- B
| \     |
|   \   |
C ----- D

Several combinations of edges may connect all four vertices without cycles. Each valid combination is a spanning tree.

What Makes a Spanning Tree Minimum?

When every edge has a weight, we calculate the total weight of a spanning tree by adding the weights of all selected edges.

Edge A-B = 2
Edge A-C = 3
Edge B-D = 4

Total MST weight = 2 + 3 + 4 = 9

A different spanning tree might have a total weight of 11. The tree with total weight 9 would therefore be a minimum spanning tree for this graph.

Important MST Properties

Minimum Spanning Tree Example

Consider this weighted graph:

        1
    A ------- B
    |         |
  4 |         | 2
    |         |
    C ------- D
        3

A ------- D = 5

The edges have the following weights:

• A-B = 1
• B-D = 2
• C-D = 3
• A-C = 4
• A-D = 5

One minimum spanning tree is:

A-B = 1
B-D = 2
C-D = 3

Total = 6

These three edges connect all four vertices and contain no cycle. Since four vertices require exactly three edges in a spanning tree, this forms a valid MST.

Kruskal's Algorithm

Kruskal's algorithm builds the minimum spanning tree by considering edges in increasing order of their weight.

For every edge, the algorithm asks whether adding that edge would create a cycle. If it does not create a cycle, the edge is included in the MST.

The basic process is:

1. Sort all edges by increasing weight.
2. Start with an empty MST.
3. Consider the smallest remaining edge.
4. Check whether adding the edge creates a cycle.
5. If no cycle is created, add the edge to the MST.
6. Continue until the MST contains V - 1 edges.

Kruskal's Algorithm Step by Step

Suppose the sorted edges are:

A-B = 1
B-D = 2
C-D = 3
A-C = 4
A-D = 5

Select A-B because it has the smallest weight.

MST:
A-B = 1

Next, select B-D:

MST:
A-B = 1
B-D = 2

Next, C-D connects C to the existing component:

MST:
A-B = 1
B-D = 2
C-D = 3

All four vertices are now connected using three edges, so the MST is complete.

Union-Find in Kruskal's Algorithm

Kruskal's algorithm needs an efficient way to determine whether two vertices already belong to the same connected component. This prevents adding an edge that would create a cycle.

A Disjoint Set Union (DSU), also called Union-Find, is commonly used for this purpose. It supports operations such as finding the representative of a component and joining two components.

If find(A) === find(B):
    A and B are already connected
    Adding A-B would create a cycle

Otherwise:
    Add A-B
    Union(A, B)

Kruskal's Algorithm in JavaScript

class UnionFind {
  constructor(vertices) {
    this.parent = {};
    this.rank = {};

    for (const vertex of vertices) {
      this.parent[vertex] = vertex;
      this.rank[vertex] = 0;
    }
  }

  find(vertex) {
    if (this.parent[vertex] !== vertex) {
      this.parent[vertex] =
        this.find(this.parent[vertex]);
    }

    return this.parent[vertex];
  }

  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);

    if (rootA === rootB) {
      return false;
    }

    if (this.rank[rootA] < this.rank[rootB]) {
      this.parent[rootA] = rootB;
    } else if (this.rank[rootA] > this.rank[rootB]) {
      this.parent[rootB] = rootA;
    } else {
      this.parent[rootB] = rootA;
      this.rank[rootA]++;
    }

    return true;
  }
}

function kruskal(vertices, edges) {
  const sortedEdges = [...edges].sort(
    (a, b) => a.weight - b.weight
  );

  const unionFind = new UnionFind(vertices);
  const mst = [];
  let totalWeight = 0;

  for (const edge of sortedEdges) {
    const { from, to, weight } = edge;

    if (unionFind.union(from, to)) {
      mst.push(edge);
      totalWeight += weight;

      if (mst.length === vertices.length - 1) {
        break;
      }
    }
  }

  return {
    edges: mst,
    totalWeight
  };
}

const vertices = ["A", "B", "C", "D"];

const edges = [
  { from: "A", to: "B", weight: 1 },
  { from: "B", to: "D", weight: 2 },
  { from: "C", to: "D", weight: 3 },
  { from: "A", to: "C", weight: 4 },
  { from: "A", to: "D", weight: 5 }
];

console.log(kruskal(vertices, edges));

Prim's Algorithm

Prim's algorithm takes a different approach. Instead of sorting all edges globally, it starts from one vertex and gradually grows a tree by adding the cheapest edge that connects the current tree to an unvisited vertex.

The algorithm can be summarized as:

1. Choose a starting vertex.
2. Mark it as part of the growing tree.
3. Find the minimum-weight edge connecting the tree to an unvisited vertex.
4. Add that edge and vertex to the tree.
5. Repeat until every vertex belongs to the tree.

Prim's Algorithm Example

Using the same graph, start from A:

Start:
A

Available edges:
A-B = 1
A-C = 4
A-D = 5

Choose:
A-B = 1

The tree now contains A and B. The cheapest edge leading to an unvisited vertex is B-D = 2:

Tree:
A -- B -- D

Selected:
A-B = 1
B-D = 2

Finally, C-D = 3 connects C:

Tree:
A -- B -- D -- C

Total weight = 1 + 2 + 3 = 6

Prim's Algorithm with a Min-Heap

A priority queue can efficiently select the cheapest edge connecting the current tree to an unvisited vertex.

function prim(graph, start) {
  const visited = new Set();
  const minHeap = [];
  const mst = [];
  let totalWeight = 0;

  function push(edge) {
    minHeap.push(edge);
    minHeap.sort((a, b) => a.weight - b.weight);
  }

  push({
    from: null,
    to: start,
    weight: 0
  });

  while (minHeap.length > 0) {
    const edge = minHeap.shift();
    const { from, to, weight } = edge;

    if (visited.has(to)) {
      continue;
    }

    visited.add(to);

    if (from !== null) {
      mst.push(edge);
      totalWeight += weight;
    }

    for (const nextEdge of graph[to]) {
      if (!visited.has(nextEdge.to)) {
        push(nextEdge);
      }
    }
  }

  return {
    edges: mst,
    totalWeight
  };
}

const graph = {
  A: [
    { from: "A", to: "B", weight: 1 },
    { from: "A", to: "C", weight: 4 },
    { from: "A", to: "D", weight: 5 }
  ],
  B: [
    { from: "B", to: "A", weight: 1 },
    { from: "B", to: "D", weight: 2 }
  ],
  C: [
    { from: "C", to: "A", weight: 4 },
    { from: "C", to: "D", weight: 3 }
  ],
  D: [
    { from: "D", to: "B", weight: 2 },
    { from: "D", to: "C", weight: 3 },
    { from: "D", to: "A", weight: 5 }
  ]
};

console.log(prim(graph, "A"));

The example uses JavaScript array sorting as a simple priority queue demonstration. For production-scale graphs, a proper binary min-heap avoids repeatedly sorting the entire queue.

Kruskal vs Prim

MST vs Shortest Path

A minimum spanning tree and a shortest path solve different optimization problems. They are often confused because both involve weighted graphs.

MST for a Disconnected Graph

A traditional minimum spanning tree requires a connected graph. If the graph is disconnected, it is impossible to create one tree containing every vertex.

Instead, the result is called a minimum spanning forest. It contains one minimum spanning tree for each connected component.

Unique and Multiple MSTs

A graph can have more than one minimum spanning tree when different edges have equal weights.

The trees may contain different edges while still having exactly the same minimum total weight. Therefore, an MST is not necessarily unique.

Applications of Minimum Spanning Trees

Time Complexity

The time complexity depends on the algorithm and graph representation.

Here, V represents the number of vertices and E represents the number of edges. For Kruskal's algorithm, sorting E edges gives O(E log E), while the Union-Find operations are highly efficient with path compression and union by rank.

Important MST Properties

Cut Property

The cut property states that for a cut dividing the vertices into two groups, a minimum-weight edge crossing that cut can be included in some minimum spanning tree. This principle is one of the foundations behind greedy MST algorithms.

Cycle Property

For a cycle in a weighted graph, a strictly heaviest edge in that cycle cannot be part of a minimum spanning tree. This property helps explain why MST algorithms avoid unnecessary expensive edges when a cheaper connection is available.

Common Beginner Mistakes

• Confusing a minimum spanning tree with a shortest path.
• Forgetting that an MST for V vertices contains exactly V - 1 edges.
• Adding an edge in Kruskal's algorithm without checking for a cycle.
• Forgetting to sort edges before applying the standard Kruskal approach.
• Using a directed graph when the standard MST problem assumes an undirected graph.
• Assuming an MST is always unique.
• Using an MST when the actual problem asks for a shortest route between two vertices.
• Forgetting that a disconnected graph produces a minimum spanning forest rather than one MST.

MST Interview Pattern

In coding interviews, an MST problem often contains clues such as:

• Connect every location, node, or computer.
• Minimize the total cost of the connections.
• Each connection has a cost or weight.
• No redundant cycles are required.
• Every vertex must become part of the connected network.

If the goal is to connect all vertices with minimum total edge cost, think about Minimum Spanning Tree. If the problem instead asks for the cheapest route between specific vertices, a shortest-path algorithm may be the appropriate pattern.

Key Takeaways

• A minimum spanning tree connects every vertex of a connected weighted undirected graph.
• An MST contains exactly V - 1 edges and no cycles.
• The objective is to minimize the total weight of the selected edges.
• Kruskal's algorithm sorts edges and uses Union-Find to avoid cycles.
• Prim's algorithm grows an MST from a starting vertex using the cheapest available connection.
• Kruskal typically runs in O(E log E).
• Prim with a binary heap and adjacency list typically runs in O((V + E) log V).
• A disconnected graph produces a minimum spanning forest.
• An MST is different from a shortest path.
• Multiple different MSTs can exist when equal-weight edges provide alternative solutions.