ProgramGuru

Minimum Spanning Tree in Graphs

Problem and examples

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected, and weighted graph that connects all the vertices with the minimum total edge weight and without any cycles.

The MST ensures that:

  • All vertices are connected.
  • The total weight of the selected edges is minimized.
  • No cycles are formed (it remains a tree).

MSTs are used in various applications like network design (telephone, electrical, or computer networks), clustering, and approximations of NP-hard problems.

Graph (Edges) Vertices MST Weight Description
[(0,1,1), (1,2,2), (0,2,3)] 3 3 Choose edges (0-1) and (1-2); skip (0-2) to avoid cycle
[(0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4)] 4 19 MST includes edges (2-3), (0-3), (0-1)
[] 0 0 Empty graph, no vertices or edges
[(0,1,5)] 2 5 Only one edge, automatically forms MST
[(0,1,1), (1,2,1), (0,2,2), (2,3,1), (3,4,1), (2,4,3)] 5 4 MST includes (0-1), (1-2), (2-3), (3-4)

How it works

Understanding the Problem

We are given an undirected, connected graph where each edge has a weight (or cost). The goal is to construct a Minimum Spanning Tree (MST) — a subgraph that:

  • Connects all the vertices (no node is left out),
  • Uses exactly V - 1 edges (where V is the number of vertices),
  • Has the minimum total edge weight among all such possible trees,
  • Contains no cycles.

This is a classical graph problem that appears often in real-world scenarios like designing cost-effective network layouts (roads, electrical grids, etc.).

Step-by-Step Solution with Example

step 1: Choose the right algorithm

There are two common greedy algorithms for MST:

  • Kruskal’s Algorithm – Works by choosing the smallest edge first. Good for sparse graphs.
  • Prim’s Algorithm – Starts from a node and grows the MST by always selecting the smallest connecting edge. Better for dense graphs.

We’ll use Kruskal’s Algorithm for this example.

step 2: Understand the given example

Consider this graph:


Nodes: 0, 1, 2, 3
Edges:
(0 - 1, weight 10)
(0 - 2, weight 6)
(0 - 3, weight 5)
(1 - 3, weight 15)
(2 - 3, weight 4)

step 3: Sort all edges by weight

We sort the edges in ascending order of weights:

  • (2 - 3, weight 4)
  • (0 - 3, weight 5)
  • (0 - 2, weight 6)
  • (0 - 1, weight 10)
  • (1 - 3, weight 15)

step 4: Initialize Disjoint Set Union (DSU)

Each node is in its own set. We'll merge sets as we add edges, avoiding cycles.

step 5: Add edges one by one

  1. Add (2 - 3, weight 4): No cycle. Add to MST.
  2. Add (0 - 3, weight 5): No cycle. Add to MST.
  3. Add (0 - 2, weight 6): Would create a cycle (0 connected to 3, which connects to 2). Skip.
  4. Add (0 - 1, weight 10): No cycle. Add to MST.

MST now includes edges: (2 - 3), (0 - 3), (0 - 1). Total weight = 4 + 5 + 10 = 19

Edge Cases

  • Disconnected Graph: No MST is possible if the graph is not fully connected.
  • Multiple equal weight edges: Both Kruskal’s and Prim’s can still work as long as we prevent cycles.
  • Negative weights: MST algorithms handle negative weights fine as long as no cycle is formed.
  • Self-loops or multiple edges between same nodes: Ignore self-loops. Use the minimum weight edge between two nodes.

Finally

Finding the Minimum Spanning Tree ensures the most efficient way to connect all points in a network without redundancy. By understanding the problem and using greedy strategies like Kruskal's or Prim's, we can solve it efficiently.

Remember to visualize the graph, sort or prioritize edges properly, and use Disjoint Set (for Kruskal) or Priority Queue (for Prim) wisely. Handling edge cases ensures that your algorithm works on all types of graphs.

  1. Sort all edges of the graph in non-decreasing order of weight (Kruskal) or initialize a min-heap with edges connected to a starting vertex (Prim).
  2. Create a data structure to keep track of connected components (DSU) or visited vertices.
  3. Iteratively select the minimum weight edge that connects new vertices (no cycles in Kruskal, no revisits in Prim).
  4. Add this edge to the MST set and update your structure.
  5. Repeat until the MST includes exactly V - 1 edges, where V is the number of vertices.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

struct Edge {
    int src, dest, weight;
};

int parent[MAX];

int find(int i) {
    if (parent[i] != i)
        parent[i] = find(parent[i]);
    return parent[i];
}

void unionSets(int u, int v) {
    int setU = find(u);
    int setV = find(v);
    parent[setU] = setV;
}

int compare(const void *a, const void *b) {
    return ((struct Edge *)a)->weight - ((struct Edge *)b)->weight;
}

int main() {
    int V = 4, E = 5;
    struct Edge edges[] = {
        {0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}
    };

    for (int i = 0; i < V; i++) parent[i] = i;

    qsort(edges, E, sizeof(edges[0]), compare);

    int totalWeight = 0;
    printf("Edges in MST:\n");
    for (int i = 0, count = 0; count < V - 1 && i < E; i++) {
        if (find(edges[i].src) != find(edges[i].dest)) {
            printf("%d - %d\n", edges[i].src, edges[i].dest);
            totalWeight += edges[i].weight;
            unionSets(edges[i].src, edges[i].dest);
            count++;
        }
    }

    printf("Total weight: %d\n", totalWeight);
    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, w;
};

vector<int> parent;

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

bool unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return false;
    parent[rootY] = rootX;
    return true;
}

int main() {
    int V = 4;
    vector<Edge> edges = {
        {0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}
    };

    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.w < b.w;
    });

    parent.resize(V);
    for (int i = 0; i < V; ++i) parent[i] = i;

    int totalWeight = 0;
    cout << "Edges in MST:\n";
    for (const auto& e : edges) {
        if (unionSets(e.u, e.v)) {
            cout << e.u << " - " << e.v << "\n";
            totalWeight += e.w;
        }
    }
    cout << "Total weight: " << totalWeight << endl;
    return 0;
}

Python implementation

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        self.parent[rootY] = rootX
        return True

def kruskal_mst(V, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(V)
    total_weight = 0
    mst = []
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v))
            total_weight += w
    return total_weight, mst

V = 4
edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
total, mst = kruskal_mst(V, edges)
print("Edges in MST:", mst)
print("Total weight:", total)

Java implementation

import java.util.*;

class Edge {
    int u, v, w;
    Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
}

class KruskalMST {
    static int find(int[] parent, int x) {
        if (parent[x] != x)
            parent[x] = find(parent, parent[x]);
        return parent[x];
    }

    static boolean union(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX == rootY) return false;
        parent[rootY] = rootX;
        return true;
    }

    public static void main(String[] args) {
        int V = 4;
        List<Edge> edges = Arrays.asList(
            new Edge(0, 1, 10), new Edge(0, 2, 6), new Edge(0, 3, 5),
            new Edge(1, 3, 15), new Edge(2, 3, 4)
        );

        edges.sort(Comparator.comparingInt(e -> e.w));
        int[] parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;

        int totalWeight = 0;
        System.out.println("Edges in MST:");
        for (Edge e : edges) {
            if (union(parent, e.u, e.v)) {
                System.out.println(e.u + " - " + e.v);
                totalWeight += e.w;
            }
        }
        System.out.println("Total weight: " + totalWeight);
    }
}

JavaScript implementation

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }

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

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false;
    this.parent[rootY] = rootX;
    return true;
  }
}

function kruskalMST(V, edges) {
  edges.sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(V);
  const mst = [];
  let totalWeight = 0;

  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {
      mst.push([u, v]);
      totalWeight += w;
    }
  }

  return { totalWeight, mst };
}

const edges = [[0, 1, 10], [0, 2, 6], [0, 3, 5], [1, 3, 15], [2, 3, 4]];
const V = 4;
console.log("Kruskal MST:", kruskalMST(V, edges));

Go implementation

package main

import (
    "fmt"
    "sort"
)

type Edge struct {
    u, v, w int
}

type UnionFind struct {
    parent []int
}

func NewUnionFind(size int) *UnionFind {
    uf := &UnionFind{make([]int, size)}
    for i := 0; i < size; i++ {
        uf.parent[i] = i
    }
    return uf
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    if rootX == rootY {
        return false
    }
    uf.parent[rootY] = rootX
    return true
}

func kruskalMST(V int, edges []Edge) (int, []Edge) {
    sort.Slice(edges, func(i, j int) bool { return edges[i].w < edges[j].w })
    uf := NewUnionFind(V)
    mst := []Edge{}
    totalWeight := 0

    for _, e := range edges {
        if uf.Union(e.u, e.v) {
            mst = append(mst, e)
            totalWeight += e.w
        }
    }
    return totalWeight, mst
}

func main() {
    edges := []Edge{{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}}
    V := 4
    total, mst := kruskalMST(V, edges)
    fmt.Println("Edges in MST:")
    for _, e := range mst {
        fmt.Printf("%d - %d\n", e.u, e.v)
    }
    fmt.Println("Total weight:", total)
}

Rust implementation

use std::cmp::Ordering;

#[derive(Clone)]
struct Edge {
    u: usize,
    v: usize,
    w: i32,
}

fn find(parent: &mut Vec<usize>, x: usize) -> usize {
    if parent[x] != x {
        parent[x] = find(parent, parent[x]);
    }
    parent[x]
}

fn union(parent: &mut Vec<usize>, x: usize, y: usize) -> bool {
    let root_x = find(parent, x);
    let root_y = find(parent, y);
    if root_x == root_y {
        return false;
    }
    parent[root_y] = root_x;
    true
}

fn main() {
    let mut edges = vec![
        Edge { u: 0, v: 1, w: 10 },
        Edge { u: 0, v: 2, w: 6 },
        Edge { u: 0, v: 3, w: 5 },
        Edge { u: 1, v: 3, w: 15 },
        Edge { u: 2, v: 3, w: 4 },
    ];

    edges.sort_by(|a, b| a.w.cmp(&b.w));

    let mut parent: Vec<usize> = (0..4).collect();
    let mut total_weight = 0;
    println!("Edges in MST:");
    for e in edges {
        if union(&mut parent, e.u, e.v) {
            println!("{} - {}", e.u, e.v);
            total_weight += e.w;
        }
    }
    println!("Total weight: {}", total_weight);
}

Kotlin implementation

data class Edge(val u: Int, val v: Int, val w: Int)

fun find(parent: IntArray, x: Int): Int {
    if (parent[x] != x)
        parent[x] = find(parent, parent[x])
    return parent[x]
}

fun union(parent: IntArray, x: Int, y: Int): Boolean {
    val rootX = find(parent, x)
    val rootY = find(parent, y)
    if (rootX == rootY) return false
    parent[rootY] = rootX
    return true
}

fun main() {
    val edges = listOf(
        Edge(0, 1, 10), Edge(0, 2, 6), Edge(0, 3, 5),
        Edge(1, 3, 15), Edge(2, 3, 4)
    ).sortedBy { it.w }

    val parent = IntArray(4) { it }
    var totalWeight = 0

    println("Edges in MST:")
    for (e in edges) {
        if (union(parent, e.u, e.v)) {
            println("${e.u} - ${e.v}")
            totalWeight += e.w
        }
    }
    println("Total weight: $totalWeight")
}

Swift implementation

struct Edge {
    let u: Int, v: Int, w: Int
}

func find(_ parent: inout [Int], _ x: Int) -> Int {
    if parent[x] != x {
        parent[x] = find(&parent, parent[x])
    }
    return parent[x]
}

func union(_ parent: inout [Int], _ x: Int, _ y: Int) -> Bool {
    let rootX = find(&parent, x)
    let rootY = find(&parent, y)
    if rootX == rootY { return false }
    parent[rootY] = rootX
    return true
}

var edges = [
    Edge(u: 0, v: 1, w: 10), Edge(u: 0, v: 2, w: 6), Edge(u: 0, v: 3, w: 5),
    Edge(u: 1, v: 3, w: 15), Edge(u: 2, v: 3, w: 4)
].sorted { $0.w < $1.w }

var parent = Array(0..<4)
var totalWeight = 0

print("Edges in MST:")
for e in edges {
    if union(&parent, e.u, e.v) {
        print("(e.u) - (e.v)")
        totalWeight += e.w
    }
}
print("Total weight: \(totalWeight)")

TypeScript implementation

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(x: number, y: number): boolean {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false;
    this.parent[rootY] = rootX;
    return true;
  }
}

function kruskalMST(V: number, edges: [number, number, number][]) {
  edges.sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(V);
  const mst: [number, number][] = [];
  let totalWeight = 0;

  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {
      mst.push([u, v]);
      totalWeight += w;
    }
  }
  return { totalWeight, mst };
}

const edges: [number, number, number][] = [
  [0, 1, 10], [0, 2, 6], [0, 3, 5], [1, 3, 15], [2, 3, 4]
];
const V = 4;
console.log("Kruskal MST:", kruskalMST(V, edges));