Minimum Spanning Tree Kruskal's Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kruskal's MST edges

What is the output of the following Go code that runs Kruskal's algorithm on a graph with 4 nodes and 5 edges?

DSA Go

package main
import (
	"fmt"
	"sort"
)
type Edge struct {
	from, to, weight int
}
func find(parent []int, i int) int {
	if parent[i] != i {
		parent[i] = find(parent, parent[i])
	}
	return parent[i]
}
func union(parent []int, rank []int, x int, y int) {
	xroot := find(parent, x)
	yroot := find(parent, y)
	if rank[xroot] < rank[yroot] {
		parent[xroot] = yroot
	} else if rank[xroot] > rank[yroot] {
		parent[yroot] = xroot
	} else {
		parent[yroot] = xroot
		rank[xroot]++
	}
}
func kruskal(edges []Edge, n int) []Edge {
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})
	parent := make([]int, n)
	rank := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
		rank[i] = 0
	}
	result := []Edge{}
	for _, e := range edges {
		x := find(parent, e.from)
		y := find(parent, e.to)
		if x != y {
			result = append(result, e)
			union(parent, rank, x, y)
		}
	}
	return result
}
func main() {
	edges := []Edge{{0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}}
	mst := kruskal(edges, 4)
	for _, e := range mst {
		fmt.Printf("%d-%d:%d ", e.from, e.to, e.weight)
	}
}

A 2-3:4 0-3:5 0-1:10

B 0-3:5 2-3:4 1-3:15

C 0-1:10 0-2:6 2-3:4

D 0-2:6 0-3:5 1-3:15

💡 Hint

Sort edges by weight and pick edges that don't form a cycle.

Kruskal's algorithm sorts edges by weight and adds edges that connect different sets. The edges chosen are (2-3:4), (0-3:5), and (0-1:10).

🧠 Conceptual

intermediate

Understanding Union-Find in Kruskal's Algorithm

In Kruskal's algorithm, what is the main purpose of the union-find data structure?

A To sort the edges by their weights

B To store the final minimum spanning tree edges

C To count the total number of edges in the graph

D To keep track of which vertices are connected to avoid cycles

💡 Hint

Think about how Kruskal avoids adding edges that create loops.

The union-find structure helps detect if two vertices belong to the same connected component, preventing cycles when adding edges.

🔧 Debug

advanced

Identify the error in this Kruskal's implementation snippet

What error will this Go code snippet cause when running Kruskal's algorithm?

DSA Go

parent := make([]int, n)
for i := 0; i < n; i++ {
	parent[i] = 0
}
// rest of union-find code omitted

A The code will panic due to index out of range

B The union-find parent array is not initialized correctly, causing incorrect cycle detection

C The edges are not sorted, so MST will be incorrect

D No error, code runs correctly

💡 Hint

How should the parent array be initialized for union-find?

Each node's parent should be itself initially. Setting all to 0 means all nodes appear connected to node 0, breaking cycle detection.

❓ Predict Output

advanced

Output of MST total weight calculation

What is the total weight of the MST produced by this Go code using Kruskal's algorithm?

DSA Go

package main
import (
	"fmt"
	"sort"
)
type Edge struct {
	from, to, weight int
}
func find(parent []int, i int) int {
	if parent[i] != i {
		parent[i] = find(parent, parent[i])
	}
	return parent[i]
}
func union(parent []int, rank []int, x int, y int) {
	xroot := find(parent, x)
	yroot := find(parent, y)
	if rank[xroot] < rank[yroot] {
		parent[xroot] = yroot
	} else if rank[xroot] > rank[yroot] {
		parent[yroot] = xroot
	} else {
		parent[yroot] = xroot
		rank[xroot]++
	}
}
func kruskal(edges []Edge, n int) []Edge {
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})
	parent := make([]int, n)
	rank := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
		rank[i] = 0
	}
	result := []Edge{}
	for _, e := range edges {
		x := find(parent, e.from)
		y := find(parent, e.to)
		if x != y {
			result = append(result, e)
			union(parent, rank, x, y)
		}
	}
	return result
}
func main() {
	edges := []Edge{{0,1,7},{0,3,5},{1,2,8},{1,3,9},{1,4,7},{2,4,5},{3,4,15},{3,5,6},{4,5,8},{4,6,9},{5,6,11}}
	mst := kruskal(edges, 7)
	total := 0
	for _, e := range mst {
		total += e.weight
	}
	fmt.Println(total)
}

A 39

B 41

C 37

D 35

💡 Hint

Sum the weights of edges chosen by Kruskal's MST.

The MST edges chosen have weights 5, 5, 6, 7, 7, and 9, totaling 39.

🚀 Application

expert

Kruskal's Algorithm with Edge Cases

Given a graph with 5 nodes and edges: (0-1:1), (1-2:2), (2-3:3), (3-4:4), (4-0:5), (1-3:1), what is the MST edges output by Kruskal's algorithm?

A 0-1:1 1-3:1 1-2:2 2-3:3

B 0-1:1 1-3:1 3-4:4 4-0:5

C 0-1:1 1-3:1 1-2:2 3-4:4

D 0-1:1 1-2:2 2-3:3 3-4:4

💡 Hint

Pick edges in ascending order without forming cycles.

Kruskal picks edges with weights 1 (0-1), 1 (1-3), 2 (1-2), and 4 (3-4).

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