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

Concept Flow - Minimum Spanning Tree Kruskal's Algorithm

Start with all edges sorted by weight

↓

Pick smallest edge

↓

Check if adding edge forms cycle?

↓

Add edge to MST

↓

Repeat until MST has (V-1) edges

↓

Done

Kruskal's algorithm sorts edges by weight, then adds the smallest edge that doesn't create a cycle until the MST is complete.

Execution Sample

DSA Java

edges = [(A-B,1), (B-C,3), (A-C,2), (C-D,4)]
sort edges by weight
for each edge in sorted:
  if edge connects different sets:
    add edge to MST
    union sets

This code sorts edges by weight and adds edges to MST if they connect different sets, avoiding cycles.

Execution Table

Step	Operation	Edge Considered	Cycle Check Result	Action	MST Edges	Disjoint Sets	Visual MST State
1	Sort edges	N/A	N/A	Edges sorted by weight	[]	{A},{B},{C},{D}	Empty
2	Consider edge	A-B (1)	No cycle	Add edge	[A-B]	{A,B},{C},{D}	A-B
3	Consider edge	A-C (2)	No cycle	Add edge	[A-B, A-C]	{A,B,C},{D}	A-B, A-C
4	Consider edge	B-C (3)	Cycle detected	Discard edge	[A-B, A-C]	{A,B,C},{D}	A-B, A-C
5	Consider edge	C-D (4)	No cycle	Add edge	[A-B, A-C, C-D]	{A,B,C,D}	A-B, A-C, C-D
6	Check MST size	N/A	N/A	MST complete with 3 edges	[A-B, A-C, C-D]	{A,B,C,D}	A-B, A-C, C-D

💡 MST has (V-1)=3 edges, algorithm stops

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
MST Edges	[]	[A-B]	[A-B, A-C]	[A-B, A-C]	[A-B, A-C, C-D]	[A-B, A-C, C-D]
Disjoint Sets	{A},{B},{C},{D}	{A,B},{C},{D}	{A,B,C},{D}	{A,B,C},{D}	{A,B,C,D}	{A,B,C,D}

Key Moments - 3 Insights

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

Because adding B-C would create a cycle with nodes A, B, and C already connected. See execution_table row 4 where cycle check is 'Cycle detected' and action is 'Discard edge'.

How do disjoint sets help in cycle detection?

Disjoint sets track which nodes are connected. If two nodes of an edge are in the same set, adding that edge creates a cycle. This is shown in variable_tracker where sets merge after adding edges.

When does the algorithm stop adding edges?

It stops when MST has (V-1) edges, where V is number of vertices. Here, after step 5, MST has 3 edges for 4 nodes, so it stops as shown in execution_table row 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the state of disjoint sets?

A {A,B,C},{D}

B {A,B},{C},{D}

C {A},{B},{C},{D}

D {A,B,C,D}

💡 Hint

Check the 'Disjoint Sets' column in execution_table row 3.

At which step does the algorithm discard an edge due to cycle detection?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look for 'Discard edge' in the 'Action' column of execution_table.

If the edge C-D had weight 1 instead of 4, how would the MST edges change after step 3?

A [A-B, A-C, C-D]

B [A-B, A-C]

C [A-B, C-D]

D [C-D]

💡 Hint

Edges are added in order of increasing weight; check execution_table and variable_tracker for MST edges.

Concept Snapshot

Kruskal's Algorithm for MST:
- Sort all edges by weight ascending
- Pick smallest edge that doesn't form cycle
- Use disjoint sets to detect cycles
- Add edges until MST has V-1 edges
- Result is minimum spanning tree connecting all nodes

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. It uses disjoint sets to track connected components. The algorithm stops when the MST has one less edge than the number of vertices. This ensures the tree connects all nodes with minimum total edge weight.

Practice

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

easy

A. To detect cycles in a graph

B. To find the shortest path between two nodes

C. To find the minimum spanning tree of a graph

D. To sort the vertices of a graph

Solution

1. Step 1: Understand Kruskal's algorithm purpose

   Kruskal's algorithm is designed to find a subset of edges that connects all vertices with the minimum total edge weight and no cycles.

2. Step 2: Compare with other graph problems

   Shortest path and cycle detection are different problems solved by other algorithms like Dijkstra or DFS.

3. Final Answer:

   To find the minimum spanning tree of a graph -> Option C

4. Quick Check:

   Minimum Spanning Tree = Find minimum edges connecting all nodes [OK]

Hint: Kruskal always builds minimum spanning tree by edges [OK]

Common Mistakes:

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

2. Which Java data structure is commonly used to efficiently check and union sets in Kruskal's algorithm?

easy

A. Disjoint Set (Union-Find)

B. PriorityQueue

C. ArrayList

D. HashMap

Solution

1. Step 1: Identify the need for set operations

   Kruskal's algorithm requires checking if two vertices belong to the same set and merging sets without cycles.

2. Step 2: Match data structure to operations

   Disjoint Set (Union-Find) supports fast union and find operations, ideal for this purpose.

3. Final Answer:

   Disjoint Set (Union-Find) -> Option A

4. Quick Check:

   Union-Find = fast set checks and merges [OK]

Hint: Use Union-Find to detect cycles fast in Kruskal [OK]

Common Mistakes:

• Using ArrayList for set operations
• Confusing PriorityQueue with Union-Find
• Using HashMap which is not efficient here

3. What is the output MST edges after running Kruskal's algorithm on this graph?

Vertices: 1, 2, 3, 4
Edges with weights:
1-2: 1
1-3: 3
2-3: 2
3-4: 4
2-4: 5

medium

A. [1-2, 2-3, 3-4]

B. [1-3, 2-3, 3-4]

C. [1-2, 1-3, 2-4]

D. [1-2, 2-4, 3-4]

Solution

1. Step 1: Sort edges by weight

   Edges sorted: 1-2(1), 2-3(2), 1-3(3), 3-4(4), 2-4(5)

2. Step 2: Pick edges without cycles

   Pick 1-2, then 2-3 (no cycle), then 1-3 creates cycle so skip, pick 3-4 (no cycle), skip 2-4 (cycle)

3. Final Answer:

   [1-2, 2-3, 3-4] -> Option A

4. Quick Check:

   Edges chosen by increasing weight without cycles [OK]

Hint: Sort edges by weight, pick smallest without cycle [OK]

Common Mistakes:

• Picking edges that form cycles
• Not sorting edges by weight
• Choosing heavier edges first

4. Identify the error in this Java snippet for Kruskal's algorithm:

for (Edge e : edges) {
  if (findSet(e.u) != findSet(e.v)) {
    union(e.u, e.v);
    mst.add(e);
  }
}
Collections.sort(edges);

medium

A. Union should be called before findSet

B. Edges should be sorted before the loop

C. mst.add(e) should be outside the if condition

D. The loop should iterate over mst, not edges

Solution

1. Step 1: Check order of sorting and iteration

   Kruskal's requires edges sorted by weight before processing to pick smallest edges first.

2. Step 2: Identify mistake in code order

   Sorting is done after the loop, so edges are not processed in correct order.

3. Final Answer:

   Edges should be sorted before the loop -> Option B

4. Quick Check:

   Sort edges first, then pick edges [OK]

Hint: Sort edges before loop to pick smallest first [OK]

Common Mistakes:

• Sorting edges after processing
• Calling union before checking sets
• Adding edges outside condition

5. Given a graph with edges:

Edges: (A-B, 4), (A-C, 3), (B-C, 2), (B-D, 5), (C-D, 7), (C-E, 8), (D-E, 6)

Using Kruskal's algorithm, what is the total weight of the minimum spanning tree?

hard

A. 18

B. 14

C. 20

D. 16

Solution

1. Step 1: Sort edges by weight

   Sorted edges: B-C(2), A-C(3), A-B(4), B-D(5), D-E(6), C-D(7), C-E(8)

2. Step 2: Pick edges without cycles until all vertices connected

   Pick B-C(2), A-C(3), A-B(4) forms cycle so skip, pick B-D(5), pick D-E(6). Total edges chosen: B-C, A-C, B-D, D-E.

3. Step 3: Calculate total weight

   2 + 3 + 5 + 6 = 16. But A-B(4) skipped due to cycle, so MST edges are B-C, A-C, B-D, D-E.

4. Step 4: Re-check cycle with A-B(4)

   Actually, A-B(4) creates cycle with A-C and B-C, so skip it. MST weight is 2+3+5+6=16.

5. Final Answer:

   16 -> Option D

6. Quick Check:

   Sum of chosen edges weights = 16 [OK]

Hint: Sort edges, pick smallest without cycle, sum weights [OK]

Common Mistakes:

• Including edges that form cycles
• Misordering edges by weight
• Adding all edges without checking cycles