Minimum Spanning Tree Kruskal's Algorithm in DSA Go - Execution Trace

Concept Flow - Minimum Spanning Tree Kruskal's Algorithm

Start with all edges sorted by weight

↓

Pick smallest edge not yet chosen

↓

Check if adding edge forms cycle?

Yes→Discard edge

No↓

Add edge to MST

↓

Repeat until MST has (V-1) edges

↓

Done: MST formed

Kruskal's algorithm sorts edges by weight, then adds edges one by one if they don't form a cycle, until the MST is complete.

Execution Sample

DSA Go

edges := []Edge{{"A","B",1},{"B","C",3},{"A","C",2},{"C","D",4}}
sortEdgesByWeight(edges)
for each edge in edges {
  if !formsCycle(edge) {
    addToMST(edge)
  }
}

This code sorts edges by weight and adds them to MST if they don't create a cycle.

Execution Table

Step	Operation	Edge Considered	Cycle Check Result	MST Edges	Visual State
1	Sort edges by weight	-	-	[]	Edges sorted: (A-B:1), (A-C:2), (B-C:3), (C-D:4)
2	Consider edge	(A-B:1)	No cycle	[(A-B:1)]	MST: A-B
3	Consider edge	(A-C:2)	No cycle	[(A-B:1), (A-C:2)]	MST: A-B, A-C
4	Consider edge	(B-C:3)	Cycle detected	[(A-B:1), (A-C:2)]	MST unchanged
5	Consider edge	(C-D:4)	No cycle	[(A-B:1), (A-C:2), (C-D:4)]	MST: A-B, A-C, C-D
6	Check MST size	-	-	[(A-B:1), (A-C:2), (C-D:4)]	MST complete with 3 edges (V-1)

💡 MST formed with (V-1) edges, algorithm stops

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
MST Edges	[]	[(A-B:1)]	[(A-B:1), (A-C:2)]	[(A-B:1), (A-C:2)]	[(A-B:1), (A-C:2), (C-D:4)]	[(A-B:1), (A-C:2), (C-D:4)]
Edges Considered	[]	[(A-B:1)]	[(A-B:1), (A-C:2)]	[(A-B:1), (A-C:2), (B-C:3)]	[(A-B:1), (A-C:2), (B-C:3), (C-D:4)]	[(A-B:1), (A-C:2), (B-C:3), (C-D:4)]
Cycle Check Result	-	No	No	Yes	No	-

Key Moments - 3 Insights

Why do we discard the edge (B-C:3) even though it connects two nodes?

Because adding (B-C:3) creates a cycle with edges (A-B:1) and (A-C:2), so it is discarded as shown in step 4 of the execution_table.

How do we know when to stop adding edges to the MST?

We stop when MST has (V-1) edges, where V is number of vertices. Here, after step 5, MST has 3 edges for 4 vertices, so we stop as shown in step 6.

Why do we sort edges by weight at the start?

Sorting ensures we always pick the smallest edge first, which helps build the MST with minimum total weight, as shown in step 1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the MST Edges after step 3?

A [(A-B:1), (B-C:3)]

B [(A-B:1), (A-C:2)]

C [(A-B:1)]

D []

💡 Hint

Check the MST Edges column at step 3 in execution_table

At which step does the algorithm detect a cycle and discard an edge?

A Step 4

B Step 2

C Step 5

D Step 6

💡 Hint

Look for 'Cycle detected' in Cycle Check Result column in execution_table

If the edge (C-D:4) was removed from the graph, what would happen to the MST?

A MST would include (B-C:3) instead

B MST would be the same

C MST would have only 2 edges and be incomplete

D Algorithm would stop earlier

💡 Hint

Check variable_tracker for MST Edges and consider that MST needs (V-1) edges

Concept Snapshot

Kruskal's Algorithm:
- Sort all edges by weight
- Pick smallest edge that doesn't form a cycle
- Use Union-Find or cycle check
- Repeat until MST has (V-1) edges
- Result is minimum spanning tree with least total weight

Full Transcript

Kruskal's algorithm builds a minimum spanning tree by sorting edges by weight and adding them one by one if they don't create a cycle. The process stops when the MST contains one less edge than the number of vertices. The execution table shows each step: sorting edges, considering each edge, checking for cycles, adding edges to MST, and stopping when complete. Key moments include understanding why edges causing cycles are discarded, when to stop, and why sorting edges is important. The variable tracker shows how MST edges grow over steps. The visual quiz tests understanding of MST state at different steps and effects of removing 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