Minimum Spanning Tree Kruskal's Algorithm in DSA Go

Mental Model

Pick the smallest edges one by one without making loops until all points connect.

Analogy: Imagine connecting cities with roads. You want to build roads with the least total cost but still connect all cities without any circle of roads.

Graph:
  (1)---2---(2)
   |         |
   3         1
   |         |
  (3)---4---(4)

Edges sorted by weight:
[1] (2-4), [2] (1-2), [3] (1-3), [4] (3-4)

Sets:
{1}, {2}, {3}, {4}

Dry Run Walkthrough

Input: Graph with nodes 1,2,3,4 and edges: (1-2:2), (2-4:1), (1-3:3), (3-4:4)

Goal: Build a tree connecting all nodes with minimum total edge weight without cycles

Step 1: Sort edges by weight: (2-4:1), (1-2:2), (1-3:3), (3-4:4)

Edges sorted: (2-4:1) -> (1-2:2) -> (1-3:3) -> (3-4:4)
Sets: {1}, {2}, {3}, {4}

Why: We pick edges from smallest to largest to minimize total cost

Step 2: Pick edge (2-4:1), connect nodes 2 and 4

MST edges: (2-4:1)
Sets: {1}, {2,4}, {3}

Why: Connecting two different sets does not form a cycle

Step 3: Pick edge (1-2:2), connect nodes 1 and 2

MST edges: (2-4:1), (1-2:2)
Sets: {1,2,4}, {3}

Why: Connecting two different sets keeps MST cycle-free

Step 4: Pick edge (1-3:3), connect nodes 1 and 3

MST edges: (2-4:1), (1-2:2), (1-3:3)
Sets: {1,2,3,4}

Why: All nodes connected, MST complete

Step 5: Skip edge (3-4:4) because nodes 3 and 4 are already connected

MST edges: (2-4:1), (1-2:2), (1-3:3)
Sets: {1,2,3,4}

Why: Adding this edge would create a cycle

Result:

MST edges: (2-4:1) -> (1-2:2) -> (1-3:3)
Total weight: 6

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	from, to, weight int
}

type DisjointSet struct {
	parent []int
	rank   []int
}

func NewDisjointSet(n int) *DisjointSet {
	parent := make([]int, n+1)
	rank := make([]int, n+1)
	for i := 1; i <= n; i++ {
		parent[i] = i
	}
	return &DisjointSet{parent, rank}
}

func (ds *DisjointSet) Find(x int) int {
	if ds.parent[x] != x {
		ds.parent[x] = ds.Find(ds.parent[x]) // path compression
	}
	return ds.parent[x]
}

func (ds *DisjointSet) Union(x, y int) bool {
	xRoot := ds.Find(x)
	yRoot := ds.Find(y)
	if xRoot == yRoot {
		return false // already connected, would form cycle
	}
	if ds.rank[xRoot] < ds.rank[yRoot] {
		ds.parent[xRoot] = yRoot
	} else if ds.rank[xRoot] > ds.rank[yRoot] {
		ds.parent[yRoot] = xRoot
	} else {
		ds.parent[yRoot] = xRoot
		ds.rank[xRoot]++
	}
	return true
}

func Kruskal(n int, edges []Edge) []Edge {
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})
	ds := NewDisjointSet(n)
	mst := []Edge{}
	for _, e := range edges {
		if ds.Union(e.from, e.to) { // connect if no cycle
			mst = append(mst, e)
			if len(mst) == n-1 {
				break // MST complete
			}
		}
	}
	return mst
}

func main() {
	edges := []Edge{
		{1, 2, 2},
		{2, 4, 1},
		{1, 3, 3},
		{3, 4, 4},
	}
	mst := Kruskal(4, edges)
	totalWeight := 0
	fmt.Print("MST edges: ")
	for i, e := range mst {
		fmt.Printf("(%d-%d:%d)", e.from, e.to, e.weight)
		if i != len(mst)-1 {
			fmt.Print(" -> ")
		}
		totalWeight += e.weight
	}
	fmt.Printf("\nTotal weight: %d\n", totalWeight)
}

sort.Slice(edges, func(i, j int) bool { return edges[i].weight < edges[j].weight })

sort edges by weight ascending to pick smallest first

if ds.Union(e.from, e.to) { mst = append(mst, e) }

add edge only if it connects two different sets (no cycle)

if len(mst) == n-1 { break }

stop when MST has n-1 edges connecting all nodes

Output

MST edges: (2-4:1) -> (1-2:2) -> (1-3:3)

Total weight: 6

Complexity Analysis

Time: O(E log E) because sorting edges dominates and union-find operations are almost O(1)

Space: O(V) for disjoint set arrays and O(E) for edges storage

vs Alternative: Compared to Prim's algorithm which uses priority queue and adjacency list, Kruskal is simpler for sparse graphs but sorting edges can be costly for dense graphs

Edge Cases

Graph with no edges

No MST edges, result is empty

DSA Go

if len(mst) == n-1 { break }

Graph with one node

MST is empty because no edges needed

DSA Go

if len(mst) == n-1 { break }

Graph with multiple edges of same weight

Algorithm picks edges in sorted order, ties broken by stable sort

DSA Go

sort.Slice(edges, func(i, j int) bool { return edges[i].weight < edges[j].weight })

When to Use This Pattern

When you need to connect all points with minimum total cost and avoid cycles, reach for Kruskal's MST using edge sorting and union-find to detect cycles.

Common Mistakes

Mistake: Not using union-find to check cycles, causing cycles in MST
Fix: Use union-find data structure to only add edges connecting different sets

Mistake: Stopping before MST has n-1 edges
Fix: Stop only when MST has exactly n-1 edges connecting all nodes

Summary

Builds a minimum cost tree connecting all nodes without cycles by picking edges from smallest to largest.

Use when you have a weighted graph and want the cheapest way to connect all points without loops.

Sort edges by weight and use union-find to avoid cycles while adding edges.

Practice

1. What is the main goal of Kruskal's Algorithm in graph theory?

easy

A. To find the shortest path between two nodes

B. To find the minimum spanning tree connecting all vertices with the least total edge weight

C. To detect cycles in a graph

D. To sort the vertices in ascending order

Solution

1. Step 1: Understand the purpose of Kruskal's Algorithm

   Kruskal's Algorithm is designed to connect all nodes in a graph with edges that have the smallest total weight without forming cycles.

2. Step 2: Compare with other graph algorithms

   Unlike shortest path or cycle detection, Kruskal's focuses on building a minimum spanning tree, which is a tree connecting all vertices with minimum edge sum.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with the least total edge weight -> Option B

4. Quick Check:

   Minimum Spanning Tree = Kruskal's Goal [OK]

Hint: Kruskal connects all nodes with minimum total edge weight [OK]

Common Mistakes:

• Confusing MST with shortest path
• Thinking Kruskal detects cycles only
• Assuming it sorts vertices

2. Which of the following Go code snippets correctly initializes a slice of edges for Kruskal's Algorithm?

easy

A. edges := []Edge{{0, 1, 10}, {1, 2, 5}, {0, 2, 15}}

B. edges := map[int]int{0:1, 1:2, 2:3}

C. edges := [3]int{10, 5, 15}

D. edges := make([]int, 3)

Solution

1. Step 1: Identify the correct data structure for edges

   Kruskal's Algorithm requires edges with two vertices and a weight, so a slice of Edge structs is appropriate.

2. Step 2: Check each option's suitability

   edges := []Edge{{0, 1, 10}, {1, 2, 5}, {0, 2, 15}} correctly creates a slice of Edge structs with start, end, and weight. Options A, C, and D do not represent edges properly.

3. Final Answer:

   edges := []Edge{{0, 1, 10}, {1, 2, 5}, {0, 2, 15}} -> Option A

4. Quick Check:

   Slice of Edge structs = Correct initialization [OK]

Hint: Edges need start, end, weight in a slice of structs [OK]

Common Mistakes:

• Using map instead of slice for edges
• Using simple int slices without struct
• Incorrect initialization syntax

3. Given the following Go code snippet for Kruskal's Algorithm, what will be the total weight of the minimum spanning tree printed?

type Edge struct {
  u, v, weight int
}

func main() {
  edges := []Edge{{0,1,4}, {0,2,3}, {1,2,1}, {1,3,2}, {2,3,4}, {3,4,2}}
  // Assume union-find and sorting implemented correctly
  // MST edges chosen: (1,2), (1,3), (3,4), (0,2)
  totalWeight := 1 + 2 + 2 + 3
  fmt.Println(totalWeight)
}

medium

A. 9

B. 7

C. 10

D. 8

Solution

1. Step 1: Sum the weights of chosen MST edges

   The edges chosen are (1,2)=1, (1,3)=2, (3,4)=2, (0,2)=3. Adding these: 1 + 2 + 2 + 3 = 8.

2. Step 2: Verify the total weight printed

   The code sums these weights and prints totalWeight. The sum is 8, which corresponds to 8.

3. Step 3: Recalculate carefully

   1 + 2 = 3, 3 + 2 = 5, 5 + 3 = 8. So total is 8.

4. Final Answer:

   8 -> Option D

5. Quick Check:

   Sum MST edges weights = 8 [OK]

Hint: Add weights of MST edges chosen carefully [OK]

Common Mistakes:

• Adding weights incorrectly
• Confusing edges chosen
• Ignoring union-find correctness

4. Identify the bug in this Go code snippet implementing Kruskal's Algorithm:

type Edge struct {
  u, v, weight int
}

func find(parent []int, i int) int {
  if parent[i] == i {
    return i
  }
  return find(parent, parent[i])
}

func union(parent []int, x, y int) {
  xset := find(parent, x)
  yset := find(parent, y)
  parent[xset] = yset
}

func main() {
  edges := []Edge{{0,1,10}, {0,2,6}, {0,3,5}, {1,3,15}, {2,3,4}}
  parent := make([]int, 4)
  for i := 0; i < 4; i++ {
    parent[i] = i
  }
  // Missing sorting edges by weight
  for _, edge := range edges {
    x := find(parent, edge.u)
    y := find(parent, edge.v)
    if x != y {
      union(parent, x, y)
      fmt.Println(edge)
    }
  }
}

medium

A. Edges are not sorted by weight before processing

B. Union function does not update parent correctly

C. Find function does not use path compression

D. Parent slice is not initialized

Solution

1. Step 1: Check the Kruskal's Algorithm requirements

   Kruskal's requires edges to be sorted by weight ascending before processing to ensure minimum total weight.

2. Step 2: Analyze the code for sorting

   The code does not sort edges before the loop, so edges are processed in input order, which can lead to incorrect MST.

3. Final Answer:

   Edges are not sorted by weight before processing -> Option A

4. Quick Check:

   Sorting edges first = Required for correct MST [OK]

Hint: Always sort edges by weight before union-find steps [OK]

Common Mistakes:

• Skipping edge sorting
• Ignoring union-find path compression
• Incorrect parent initialization

5. You have a graph with vertices 0 to 5 and edges:

(0,1,4), (0,2,3), (1,2,1), (1,3,2), (2,3,4), (3,4,2), (4,5,6), (3,5,1)

Using Kruskal's Algorithm, which edges will be included in the minimum spanning tree?

hard

A. (1,2), (3,5), (1,3), (3,4), (0,2), (4,5)

B. (0,1), (1,3), (3,4), (4,5), (3,5), (2,3)

C. (1,2), (1,3), (3,5), (3,4), (0,2)

D. (0,2), (1,2), (1,3), (3,4), (3,5), (4,5)

Solution

1. Step 1: Sort edges by weight ascending

   Edges sorted: (1,2,1), (3,5,1), (1,3,2), (3,4,2), (0,2,3), (0,1,4), (2,3,4), (4,5,6)

2. Step 2: Pick edges without forming cycles

   Pick (1,2), (3,5), (1,3), (3,4), (0,2) - these connect all vertices without cycles. Skip (4,5) as it forms a cycle (4 and 5 already connected via 3).

3. Final Answer:

   (1,2), (1,3), (3,5), (3,4), (0,2) -> Option C

4. Quick Check:

   Sorted edges + no cycles = MST edges [OK]

Hint: Sort edges, pick smallest without cycles until all connected [OK]

Common Mistakes:

• Including edges that form cycles
• Not sorting edges properly
• Missing last vertex connection