Kruskal’s Algorithm: Minimum Spanning Tree

Kruskal’s algorithm finds the minimum spanning tree(MST) for the given graph. It sorts edges by ascending edge weight and follows greedy approach by repeatedly picking the least weight edge to build the MST. For each selected edge, it performs union find algorithm to determine if the two nodes connected by the edge are already connected or can be unified. A MST is constructed as the number of edges equals to the number of nodes -1 in the tree.

Kruskal’s algorithm summary card

Table of Contents
· Spanning Tree
· Minimum Spanning Tree(MST)
· How Does Kruskal’s Algorithm Work?
· Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Golang
  ∘ Python
· LeetCode 1584: Min Cost to Connect All Points
  ∘ Complexity
  ∘ Golang
  ∘ Python

Spanning Tree

A spanning tree is a subgraph of an undirected connected graph. It contains the same number of vertices(v) as the graph and the number of vertices -1(v-1) edges. There is no cycle/loop present in the tree. A connected graph may have multiple spanning trees. However, a disconnected graph has no any spanning tree.

spanning tree

Minimum Spanning Tree(MST)

A spanning tree has the minimum sum of all edge weights among all other possible spanning trees of the same graph.

minimum spanning tree

How Does Kruskal’s Algorithm Work?

tree and set are interchangeable here

Kruskal’s algorithm finds the minimum spanning tree(MST) for the given graph. This algorithm is a union find application because it implements find operation to check if nodes are in the same tree/set and perform union operation to merge two disjoint trees/sets.

You can check Union Find Algorithm here for details.

Originally each node in the graph is a tree that only contains itself. Then the edge with the least weight is selected and look at the two nodes connected by the currently picking edge. If the two nodes are not in the same tree, merge the two trees to the a single tree. Otherwise, discard the edge because the nodes are already connected. A MST with v nodes is built as it contains (v-1) edges.

Kruskal’s algorithm is also a greedy algorithm since it repeatedly picks the edge with the minimum weight to build the MST.

Graphical Explanation

graph

• step1: Sort edges by ascending edge weight
• step2: Initialize parent and size arrays with the length of the total number of nodes.

parent: store a node's root parent
size: store the total number of nodes in a subtree
step2.a: originally every node is a root node to itself
         parent[i] = i
step2.b: originally every tree/set contains a single node
         size[i] = 1

1

• step3: Initialize a variable edgeCount to 0

edgeCount: track the number of edges in the currently built MST
edgeCount = 0

• step4: Pick the smallest edge

step4.a: find root parent and check if two nodes are in the same tree
root1 == root2?
- Yes → in the same set → return false
- No → step4.b
step4.b: merge the smaller tree to the larger tree
parent[root1] = root2 or parent[root2] = root1
step4.c: increment the size of the larger tree by 1
size[root2] += 1 or size[root1] += 1
→ return true
step4.d: increment edgeCount by 1 if return true

2

• step5: repeat step4 until it includes (the number of nodes -1) edges in the MST

edgeCount == numOfNodes - 1 → stop

3 and 4

5 and 6

Code Implementation

Complexity

Time: O(elog(e) + elog(v))

elog(e): sort all the edges
elog(v): iterate through all edges(e) and perform union find (find operation: log(v))

Space: O(v) parent and size array
v: the total number of vertices
e: the total number of edges

Golang

Python

LeetCode 1584: Min Cost to Connect All Points

Complexity

Time: O(n² log(n))

log(n²) = 2 log(n)

Space: O(n²)
n: the total number of points

Golang

Python

You can access the source code here.

LeetCode Problem:

• 1584: Min Cost to Connect All Points

Related story:

• Union Find Algorithm

Reference:

• Kruskal’s algorithm