Minimum Spanning Tree Kruskal's Algorithm in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the parent array for union-find.

DSA Go

parent := make([]int, n)
for i := 0; i < n; i++ {
    parent[i] = [1]
}

Drag options to blanks, or click blank then click option'

Ai

B0

C-1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Setting all parents to 0 causes incorrect union-find behavior.

Using -1 or n as parent values breaks the logic.

Each node is initially its own parent, so parent[i] = i.

2fill in blank

medium

Complete the code to find the root parent of a node with path compression.

DSA Go

func find(parent []int, x int) int {
    if parent[x] != x {
        parent[x] = [1](parent, parent[x])
    }
    return parent[x]
}

Drag options to blanks, or click blank then click option'

Aparent

Bunion

Croot

Dfind

Attempts:

3 left

💡 Hint

Common Mistakes

Calling union instead of find causes errors.

Using parent directly without recursion breaks path compression.

The find function calls itself recursively to find the root parent and compress the path.

3fill in blank

hard

Fix the error in the union function to correctly merge two sets.

DSA Go

func union(parent []int, a, b int) {
    rootA := find(parent, a)
    rootB := find(parent, b)
    if rootA != rootB {
        parent[rootB] = [1]
    }
}

Drag options to blanks, or click blank then click option'

Ab

Ba

CrootA

DrootB

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[rootB] = b or a causes incorrect unions.

Assigning parent[rootB] = rootB does nothing.

To merge sets, set the parent of rootB to rootA.

4fill in blank

hard

Fill both blanks to check if adding an edge creates a cycle and to union sets if not.

DSA Go

for _, edge := range edges {
    if find(parent, edge.u) [1] find(parent, edge.v) {
        union(parent, edge.u, edge.v)
        mstWeight += edge.weight
    }
}

Drag options to blanks, or click blank then click option'

A==

B!=

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' causes cycles by adding edges within the same set.

Using '<' or '>' is not meaningful for root comparison.

We add the edge only if the roots of u and v are different to avoid cycles.

5fill in blank

hard

Fill all three blanks to sort edges by weight, initialize MST weight, and iterate edges.

DSA Go

sort.Slice(edges, func(i, j int) bool {
    return edges[i].[1] < edges[j].[2]
})
mstWeight := [3]
for _, edge := range edges {
    if find(parent, edge.u) != find(parent, edge.v) {
        union(parent, edge.u, edge.v)
        mstWeight += edge.weight
    }
}

Drag options to blanks, or click blank then click option'

Aweight

C0

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by u or other fields breaks MST correctness.

Not initializing mstWeight causes wrong total weight.

Sort edges by their weight field, initialize mstWeight to 0 before 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