SimuVedaAlgorithms Lab Open in the lab

Graphs / Advanced

Kruskal's Minimum Spanning Tree Visualizer

Sort edges by weight. Take each edge unless its two ends are already connected. Union-find answers "already connected?" almost instantly.

Start the Kruskal's Minimum Spanning Tree simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(E log E)
Average timeO(E log E)
Worst timeO(E log E)
Extra spaceO(V)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Sort the edges from lightest to heaviest. Every node starts as its own group.
  2. Next lightest edge: B–C (1). Are B and C in different groups?
  3. Yes. Add the edge and merge the groups. Total = 1.
  4. Next lightest edge: A–C (2). Are A and C in different groups?
  5. Yes. Add the edge and merge the groups. Total = 3.
  6. Next lightest edge: D–E (2). Are D and E in different groups?
  7. Yes. Add the edge and merge the groups. Total = 5.
  8. Next lightest edge: E–F (3). Are E and F in different groups?
  9. Yes. Add the edge and merge the groups. Total = 8.
  10. Next lightest edge: A–B (4). Are A and B in different groups?
  11. No, they are already connected. This edge would make a cycle, so skip it.
  12. Next lightest edge: B–D (5). Are B and D in different groups?
  13. Yes. Add the edge and merge the groups. Total = 13.
  14. 5 edges chosen, so the tree is complete. Total weight: 13.

Try it with your own input →

Kruskal's minimum spanning tree in Java, Python, C++, C and JavaScript

int kruskal(List<Edge> edges, int n) {
  edges.sort((a, b) -> a.w - b.w);
  UnionFind uf = new UnionFind(n);
  int total = 0;
  for (Edge e : edges) {
    if (uf.find(e.u) != uf.find(e.v)) {
      uf.union(e.u, e.v);
      total += e.w;
    }
  }
  return total;
}
def kruskal(edges, n):
    edges.sort(key=lambda e: e[2])
    parent, rank = list(range(n)), [0] * n
    total = 0
    for u, v, w in edges:
        if find(parent, u) != find(parent, v):
            union(parent, rank, u, v)
            total += w
    return total
struct Edge { int u, v, w; };

int kruskal(vector<Edge> edges, int n) {
  sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
  parent.resize(n); iota(parent.begin(), parent.end(), 0); rnk.assign(n, 0);
  int total = 0;
  for (const Edge& e : edges) {
    if (find(e.u) != find(e.v)) {
      unite(e.u, e.v);
      total += e.w;
    }
  }
  return total;
}
#include <stdlib.h>
struct Edge { int u, v, w; };

int byWeight(const void* a, const void* b) {
  return ((const struct Edge*)a)->w - ((const struct Edge*)b)->w;
}
/* find and unite are from "Union-find" */
int kruskal(struct Edge edges[], int m, int n) {
  qsort(edges, m, sizeof(struct Edge), byWeight);
  for (int i = 0; i < n; i++) { parent[i] = i; rnk[i] = 0; }
  int total = 0;
  for (int k = 0; k < m; k++) {
    if (find(edges[k].u) != find(edges[k].v)) {
      unite(edges[k].u, edges[k].v);
      total += edges[k].w;
    }
  }
  return total;
}
function kruskal(edges, n) {
  edges.sort((a, b) => a.w - b.w);
  const parent = [...Array(n).keys()], rank = new Array(n).fill(0);
  let total = 0;
  for (const e of edges) {
    if (find(parent, e.u) !== find(parent, e.v)) {
      union(parent, rank, e.u, e.v);
      total += e.w;
    }
  }
  return total;
}

In an interview

LeetCode 1584, Min Cost to Connect All Points. Union-find alone solves 547 Number of Provinces and 684 Redundant Connection.

Watch the Parent row: that is the union-find structure. find() follows parents to a root; union() links one root under another.

More graphs