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) and find(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, .