Kruskal's Algorithm - Full Guide

Overview

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a graph. It works by selecting the shortest edges and ensuring no cycles are formed until all vertices are connected.

Algorithm Steps

1. Sort all edges in non-decreasing order of their weights.
2. Initialize a disjoint-set (Union-Find) for cycle detection.
3. Iterate over the sorted edges:
• If the edge connects two different sets, include it in the MST and union the sets.
4. Repeat until MST has (V - 1) edges.

Time and Memory Complexity

• Time Complexity: O(E log E + E α(V)) ≈ O(E log E), where E is the number of edges and α is the inverse Ackermann function.
• Space Complexity: O(V) for storing parent and rank arrays.

Code Template (C++)

struct Edge {
  int u, v, weight;
  bool operator<(const Edge& e) const {
    return weight < e.weight;
  }
};

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

void unite(vector& parent, vector& rank, int x, int y) {
  int xr = find(parent, x);
  int yr = find(parent, y);
  if (xr != yr) {
    if (rank[xr] < rank[yr]) parent[xr] = yr;
    else if (rank[xr] > rank[yr]) parent[yr] = xr;
    else { parent[yr] = xr; rank[xr]++; }
  }
}

int kruskal(int n, vector& edges) {
  sort(edges.begin(), edges.end());
  vector parent(n), rank(n, 0);
  iota(parent.begin(), parent.end(), 0);

  int mst_weight = 0;
  for (Edge& e : edges) {
    if (find(parent, e.u) != find(parent, e.v)) {
      unite(parent, rank, e.u, e.v);
      mst_weight += e.weight;
    }
  }
  return mst_weight;
}

Easy Problems

1. Find the MST of an Undirected Graph

// Input: 4 vertices, 5 edges
// Output: MST weight
int main() {
  vector edges = {{0,1,10}, {0,2,6}, {0,3,5}, {1,3,15}, {2,3,4}};
  cout << kruskal(4, edges); // Output: 19
}

2. Check if a graph is connected using Kruskal

bool isConnected(int n, vector& edges) {
  sort(edges.begin(), edges.end());
  vector parent(n), rank(n, 0);
  iota(parent.begin(), parent.end(), 0);

  int edge_count = 0;
  for (Edge& e : edges) {
    if (find(parent, e.u) != find(parent, e.v)) {
      unite(parent, rank, e.u, e.v);
      edge_count++;
    }
  }
  return edge_count == n - 1;
}

Intermediate Problems

1. Second Best MST

// Compute all MSTs excluding one edge at a time
int secondBestMST(int n, vector edges) {
  sort(edges.begin(), edges.end());
  vector parent(n), rank(n);
  iota(parent.begin(), parent.end(), 0);

  vector mst;
  int mst_weight = 0;
  for (Edge& e : edges) {
    if (find(parent, e.u) != find(parent, e.v)) {
      unite(parent, rank, e.u, e.v);
      mst.push_back(e);
      mst_weight += e.weight;
    }
  }

  int second_best = INT_MAX;
  for (Edge removed : mst) {
    vector p(n), r(n, 0);
    iota(p.begin(), p.end(), 0);
    int weight = 0, count = 0;
    for (Edge& e : edges) {
      if (e.u == removed.u && e.v == removed.v && e.weight == removed.weight) continue;
      if (find(p, e.u) != find(p, e.v)) {
        unite(p, r, e.u, e.v);
        weight += e.weight;
        count++;
      }
    }
    if (count == n - 1) second_best = min(second_best, weight);
  }
  return second_best;
}

2. Minimum Cost to Connect All Cities

int minimumCost(int n, vector<Edge>& edges) {
  return kruskal(n, edges);
}

Hard Problem

1. Maximum Edge Weight in MST Path Between Two Nodes

Use Kruskal to build MST, then preprocess tree for LCA with max edge weight query.

// This needs Binary Lifting (not shown fully here). Concept:
// - Build MST with Kruskal
// - Use DFS + Binary Lifting to preprocess max edge weight between nodes
// - Query max edge on path using LCA

Conclusion

Kruskal's Algorithm is a powerful and efficient method for MST-related problems. Its simplicity and performance make it a go-to choice for sparse graphs or problems where edge weights dominate computation.