Minimum Spanning Tree Kruskal's Algorithm in DSA Go - Build from Scratch

Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. Each cable has a cost. Your goal is to connect all computers with the least total cost without any loops.

🎯 Goal: Build a program that uses Kruskal's algorithm to find the minimum spanning tree (MST) of a graph. The MST connects all nodes with the smallest total edge cost.

📋 What You'll Learn

Create a list of edges with exact nodes and weights

Create a parent slice for union-find structure

Implement the union-find functions: find and union

Sort edges by weight

Select edges to build MST without cycles

Print the MST edges and their total cost

💡 Why This Matters

🌍 Real World

Network design, connecting computers or cities with minimum cable cost.

💼 Career

Useful for software engineers working on network optimization, infrastructure planning, and graph algorithms.

1

Create the graph edges

Create a slice called edges of type Edge with these exact entries: {u: 0, v: 1, weight: 4}, {u: 0, v: 2, weight: 3}, {u: 1, v: 2, weight: 1}, {u: 1, v: 3, weight: 2}, {u: 2, v: 3, weight: 4}, {u: 3, v: 4, weight: 2}, {u: 4, v: 5, weight: 6}

DSA Go

package main

type Edge struct {
    u, v, weight int
}

func main() {
    // Create the edges slice with given edges
    // Your code here
}

Hint

Define a slice of Edge structs with the exact nodes and weights given.

2

Create union-find parent slice

Create a slice called parent of type int with length 6. Initialize it so that each element is its own parent (0 to 5).

DSA Go

package main

type Edge struct {
    u, v, weight int
}

func main() {
    edges := []Edge{
        {u: 0, v: 1, weight: 4},
        {u: 0, v: 2, weight: 3},
        {u: 1, v: 2, weight: 1},
        {u: 1, v: 3, weight: 2},
        {u: 2, v: 3, weight: 4},
        {u: 3, v: 4, weight: 2},
        {u: 4, v: 5, weight: 6},
    }
    // Create parent slice with each node as its own parent
    // Your code here
}

Hint

Create a slice parent of size 6 and set each element to its own index.

3

Implement Kruskal's algorithm core logic

Implement the find function to find the parent of a node with path compression. Implement the union function to join two sets. Sort the edges slice by weight. Iterate over edges using for _, edge := range edges. For each edge, use find on edge.u and edge.v. If parents differ, use union and append the edge to a slice called mst. Also keep track of total weight in totalWeight.

DSA Go

package main

import "sort"

type Edge struct {
    u, v, weight int
}

func find(parent []int, x int) int {
    // Your code here
}

func union(parent []int, x, y int) {
    // Your code here
}

func main() {
    edges := []Edge{
        {u: 0, v: 1, weight: 4},
        {u: 0, v: 2, weight: 3},
        {u: 1, v: 2, weight: 1},
        {u: 1, v: 3, weight: 2},
        {u: 2, v: 3, weight: 4},
        {u: 3, v: 4, weight: 2},
        {u: 4, v: 5, weight: 6},
    }
    parent := make([]int, 6)
    for i := 0; i < 6; i++ {
        parent[i] = i
    }

    // Sort edges by weight
    // Iterate edges and build MST
    // Your code here
}

Hint

Write find with path compression and union to join sets. Sort edges by weight. Loop over edges, use find to check parents, and union if different. Append edges to mst and sum weights.

4

Print the MST edges and total cost

Print each edge in mst in the format "Edge: u - v, Weight: weight" using fmt.Printf. After all edges, print "Total weight: totalWeight" using fmt.Printf.

DSA Go

package main

import (
    "fmt"
    "sort"
)

type Edge struct {
    u, v, weight int
}

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

func union(parent []int, x, y int) {
    px := find(parent, x)
    py := find(parent, y)
    if px != py {
        parent[py] = px
    }
}

func main() {
    edges := []Edge{
        {u: 0, v: 1, weight: 4},
        {u: 0, v: 2, weight: 3},
        {u: 1, v: 2, weight: 1},
        {u: 1, v: 3, weight: 2},
        {u: 2, v: 3, weight: 4},
        {u: 3, v: 4, weight: 2},
        {u: 4, v: 5, weight: 6},
    }
    parent := make([]int, 6)
    for i := 0; i < 6; i++ {
        parent[i] = i
    }

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

    var mst []Edge
    totalWeight := 0

    for _, edge := range edges {
        pu := find(parent, edge.u)
        pv := find(parent, edge.v)
        if pu != pv {
            union(parent, pu, pv)
            mst = append(mst, edge)
            totalWeight += edge.weight
        }
    }

    // Print MST edges and total weight
    for _, edge := range mst {
        fmt.Printf("Edge: %d - %d, Weight: %d\n", edge.u, edge.v, edge.weight)
    }
    fmt.Printf("Total weight: %d\n", totalWeight)
}

Hint

Use a for loop to print each edge in mst with fmt.Printf. Then print the total weight.

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