Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Goal
Kruskal's algorithm (1956) builds a minimum spanning tree of a weighted graph with vertices. It is a greedy algorithm that is guaranteed to give an optimal tree.
Algorithm
Steps:
- add all vertices of to the MST, with no edges yet
- add an edge of minimum weight of
- while the MST has fewer than edges, add the edge of next minimum weight that does not make a cycle, and skip it otherwise
During the run the MST may be a forest (several small trees). It becomes one tree when the algorithm finishes.

Here the edges are taken as ; the second edge of weight is skipped because it would close a cycle; then the edge of weight completes the tree with edges.
MST Is Not Unique
When two edges have the same weight, choosing either one can lead to a different MST. All such trees have the same minimum total weight.
Detecting Cycles with a Disjoint Set
A disjoint set (union-find) tracks which vertices are already joined:
- initially each vertex is its own set, so nothing is connected and there are no cycles
- find returns the root of a vertex's set by following parent pointers until it reaches a vertex marked as its own root
- union merges two sets by making one root point to the other root
- before adding edge , compare
find(u)andfind(v): if different, add the edge and union the sets; if the same, and are already connected, so the edge would form a cycle and is skipped
Python Code
class DisjointSet:
def __init__(self, vertices):
self.parent = [-1] * vertices # all vertices disjoint at first
def find(self, node): # root of the set of node
if self.parent[node] == -1:
return node
return self.find(self.parent[node])
def union(self, x, y):
x_set, y_set = self.find(x), self.find(y)
if x_set != y_set:
self.parent[x_set] = y_set
def kruskal(V, edges): # edges: list of (u, v, weight)
edges.sort(key=lambda e: e[2]) # sort by weight
ds = DisjointSet(V)
mst = []
for u, v, w in edges:
if ds.find(u) != ds.find(v): # no cycle
mst.append((u, v, w))
ds.union(u, v)
return mst
edges = [(0,1,4), (0,2,2), (0,4,3), (1,3,5), (2,3,1),
(2,4,6), (2,5,3), (3,5,6), (4,5,2)]
print(kruskal(6, edges))
# [(2,3,1), (0,2,2), (4,5,2), (0,4,3), (0,1,4)]The MST from the code has total weight . Sorting the edges dominates the cost, .