Minimum Spanning Tree Kruskal
In this page:
What is MST
A minimum spanning tree connects every vertex in a weighted graph using the smallest possible total edge weight, with no cycles — think of it as the cheapest way to lay cable so every building is reachable, with no redundant loops.
Example: What is MST
#include <iostream>
using namespace std;
int main() {
int edges[][3] = {{0,1,4},{1,2,2},{0,2,5}};
cout << "MST: connect all vertices, no cycles, minimum total weight";
return 0;
}public class Main {
public static void main(String[] args) {
int[][] edges = {{0,1,4},{1,2,2},{0,2,5}};
System.out.println("MST: connect all vertices, no cycles, minimum total weight");
}
}edges = [(0,1,4),(1,2,2),(0,2,5)]
print("MST: connect all vertices, no cycles, minimum total weight")#include <stdio.h>
int main() {
int edges[3][3] = {{0,1,4},{1,2,2},{0,2,5}};
printf("MST: connect all vertices, no cycles, minimum total weight");
return 0;
}Login to try C/C++/Java code in the editor
Kruskal Idea
Kruskal's algorithm sorts every edge from cheapest to most expensive and walks through them in that order, adding an edge to the tree only if it doesn't create a cycle with edges already chosen.
Example: Kruskal Idea
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<vector<int>> edges = {{0,1,4},{1,2,2},{0,2,5}};
sort(edges.begin(), edges.end(), [](auto&a, auto&b){ return a[2] < b[2]; });
cout << "Cheapest edge first: " << edges[0][0] << "-" << edges[0][1] << " (w=" << edges[0][2] << ")";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[][] edges = {{0,1,4},{1,2,2},{0,2,5}};
Arrays.sort(edges, (a,b) -> a[2]-b[2]);
System.out.println("Cheapest edge first: " + edges[0][0] + "-" + edges[0][1] + " (w=" + edges[0][2] + ")");
}
}edges = [[0,1,4],[1,2,2],[0,2,5]]
edges.sort(key=lambda e: e[2])
print(f"Cheapest edge first: {edges[0][0]}-{edges[0][1]} (w={edges[0][2]})")#include <stdio.h>
int main() {
int edges[3][3] = {{0,1,4},{1,2,2},{0,2,5}};
for (int i = 0; i < 3; i++)
for (int j = i+1; j < 3; j++)
if (edges[j][2] < edges[i][2]) { int t[3]; for(int k=0;k<3;k++){t[k]=edges[i][k];edges[i][k]=edges[j][k];edges[j][k]=t[k];} }
printf("Cheapest edge first: %d-%d (w=%d)", edges[0][0], edges[0][1], edges[0][2]);
return 0;
}Login to try C/C++/Java code in the editor
Disjoint Set
A disjoint set (union-find) tracks which vertices are already connected to each other; before adding an edge, Kruskal checks whether its two endpoints are already in the same set — if they are, that edge would only form a cycle and gets skipped.
Example: Disjoint Set
#include <iostream>
using namespace std;
int parent[3] = {0,1,2};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
int main() {
int u = 0, v = 1;
if (find(u) != find(v)) { cout << "Different sets, add edge, union them"; parent[find(u)] = find(v); }
else cout << "Same set already, edge would create a cycle -- skip";
return 0;
}public class Main {
static int[] parent = {0,1,2};
static int find(int x) { return parent[x]==x ? x : find(parent[x]); }
public static void main(String[] args) {
int u = 0, v = 1;
if (find(u) != find(v)) { System.out.print("Different sets, add edge, union them"); parent[find(u)] = find(v); }
else System.out.print("Same set already, edge would create a cycle -- skip");
}
}parent = [0, 1, 2]
def find(x):
return x if parent[x] == x else find(parent[x])
u, v = 0, 1
if find(u) != find(v):
print("Different sets, add edge, union them", end="")
parent[find(u)] = find(v)
else:
print("Same set already, edge would create a cycle -- skip", end="")#include <stdio.h>
int parent[3] = {0,1,2};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
int main() {
int u = 0, v = 1;
if (find(u) != find(v)) { printf("Different sets, add edge, union them"); parent[find(u)] = find(v); }
else printf("Same set already, edge would create a cycle -- skip");
return 0;
}Login to try C/C++/Java code in the editor
Example
Picture five cities and the cost of building a road between each pair: Kruskal picks the cheapest road first, then the next cheapest that doesn't reconnect two cities already linked, continuing until all cities are joined.
Example: Example
#include <iostream>
using namespace std;
int main() {
cout << "5 cities: pick cheapest road, then next cheapest that doesn't reconnect two linked cities";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("5 cities: pick cheapest road, then next cheapest that doesn't reconnect two linked cities");
}
}print("5 cities: pick cheapest road, then next cheapest that doesn't reconnect two linked cities")#include <stdio.h>
int main() {
printf("5 cities: pick cheapest road, then next cheapest that doesn't reconnect two linked cities");
return 0;
}Login to try C/C++/Java code in the editor
Complexity
Sorting all E edges costs O(E log E), which dominates the running time since the union-find operations that follow are nearly constant time with path compression — so the overall complexity is essentially the cost of the sort.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Kruskal: O(E log E) dominated by sorting edges, union-find is nearly constant with path compression";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Kruskal: O(E log E) dominated by sorting edges, union-find is nearly constant with path compression");
}
}print("Kruskal: O(E log E) dominated by sorting edges, union-find is nearly constant with path compression")#include <stdio.h>
int main() {
printf("Kruskal: O(E log E) dominated by sorting edges, union-find is nearly constant with path compression");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: