Minimum spanning tree (Kruskal's) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Minimum spanning tree (Kruskal's)

Start with all edges sorted by weight

↓

Pick smallest edge not yet chosen

↓

Check if adding edge creates cycle?

Yes→Discard edge

No↓

Add edge to MST

↓

Have MST edges = vertices - 1?

No→Repeat picking edges

Yes↓

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

Data Structures Theory

Edges sorted by weight:
(1) A-B:1
(2) B-C:2
(3) A-C:3
(4) C-D:4
(5) B-D:5

Pick edges in order, add if no cycle.

This example shows how Kruskal's picks edges from smallest to largest, adding them if they don't create a cycle.

Analysis Table

Step	Operation	Edge Considered	Cycle Check Result	Action	MST Edges	Visual MST State
1	Sort edges	All edges	N/A	Sort edges by weight	[]	No edges selected
2	Pick edge	A-B (1)	No cycle	Add edge	[A-B]	A-B
3	Pick edge	B-C (2)	No cycle	Add edge	[A-B, B-C]	A-B, B-C
4	Pick edge	A-C (3)	Cycle detected	Discard edge	[A-B, B-C]	A-B, B-C
5	Pick edge	C-D (4)	No cycle	Add edge	[A-B, B-C, C-D]	A-B, B-C, C-D
6	Pick edge	B-D (5)	Cycle detected	Discard edge	[A-B, B-C, C-D]	A-B, B-C, C-D
7	Check MST completion	Edges count = vertices-1?	Yes	Stop	[A-B, B-C, C-D]	Final MST formed

💡 MST formed when edges count equals vertices minus one (3 edges for 4 vertices).

State Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
MST Edges	[]	[A-B]	[A-B, B-C]	[A-B, B-C]	[A-B, B-C, C-D]	[A-B, B-C, C-D]	[A-B, B-C, C-D]
Edges Considered	All edges sorted	A-B	B-C	A-C	C-D	B-D	All edges processed
Cycle Check Result	N/A	No	No	Yes	No	Yes	N/A

Key Insights - 3 Insights

Why do we discard the edge A-C even though it has a small weight?

Because adding A-C creates a cycle with edges A-B and B-C already in MST (see step 4 in execution_table). Kruskal's avoids cycles to keep MST valid.

How do we know when the MST is complete?

When the number of edges in MST equals number of vertices minus one (step 7). Here, 4 vertices need 3 edges.

What does 'cycle check' mean in Kruskal's algorithm?

It means checking if adding the current edge connects two vertices already connected by MST edges, which would form a loop (see cycle check results in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the cycle check result for edge A-C?

A No cycle

B Not checked

C Cycle detected

D Edge not considered

💡 Hint

Check the 'Cycle Check Result' column at step 4 in execution_table.

At which step does the MST reach the required number of edges?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'MST Edges' column and the exit_note about edges count.

If the edge B-D (weight 5) was considered before C-D (weight 4), what would happen?

A B-D would be discarded due to cycle

B B-D would be added to MST

C Algorithm would fail

D No change in MST

💡 Hint

Refer to cycle checks and order of edges in execution_table and variable_tracker.

Concept Snapshot

Kruskal's MST Algorithm:
- Sort edges by weight ascending
- Pick smallest edge
- Add if no cycle formed
- Repeat until MST has (vertices-1) edges
- Uses cycle detection (Union-Find or similar)
- Result is minimum total weight tree connecting all vertices

Full Transcript

Kruskal's algorithm builds a minimum spanning tree by sorting all edges by weight. It then picks edges from smallest to largest, adding each edge only if it does not create a cycle with edges already chosen. This process continues until the MST contains exactly one less edge than the number of vertices, ensuring all vertices are connected with minimum total edge weight. Cycle detection is key to avoid loops. The example shows edges considered step-by-step, cycle checks, and the MST growing until complete.

Practice

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

easy

A. To detect if a graph contains cycles

B. To find the shortest path between two vertices

C. To find the minimum spanning tree connecting all vertices without cycles

D. To sort vertices by their degree

Solution

1. Step 1: Understand the purpose of Kruskal's algorithm

   Kruskal's algorithm is designed to connect all points in a graph with the smallest total edge weight without forming any loops.

2. Step 2: Compare with other graph problems

   Unlike shortest path or cycle detection alone, Kruskal's focuses on building a minimum spanning tree, which is a tree connecting all vertices with minimal cost.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices without cycles -> Option C

4. Quick Check:

   Kruskal's goal = minimum spanning tree [OK]

Hint: Kruskal's connects all points cheaply without loops [OK]

Common Mistakes:

• Confusing minimum spanning tree with shortest path
• Thinking it detects cycles only
• Assuming it sorts vertices instead of edges

2. Which of the following is the correct first step in Kruskal's algorithm?

easy

A. Pick any vertex and start a depth-first search

B. Sort all edges in increasing order of their weights

C. Remove all vertices with degree 1

D. Sort vertices by their labels alphabetically

Solution

1. Step 1: Identify the initial step of Kruskal's algorithm

   Kruskal's algorithm begins by sorting all edges by their weight from smallest to largest to ensure the cheapest edges are considered first.

2. Step 2: Eliminate incorrect options

   Depth-first search and vertex removal are not part of Kruskal's initial steps, and sorting vertices alphabetically is irrelevant.

3. Final Answer:

   Sort all edges in increasing order of their weights -> Option B

4. Quick Check:

   First step = sort edges by weight [OK]

Hint: Always start by sorting edges by weight ascending [OK]

Common Mistakes:

• Sorting vertices instead of edges
• Starting with a search instead of sorting
• Removing vertices prematurely

3. Given the edges with weights: (A-B: 1), (B-C: 4), (A-C: 3), (C-D: 2), what edges will Kruskal's algorithm select for the minimum spanning tree?

medium

A. (A-C), (B-C), (C-D)

B. (A-B), (C-D), (B-C)

C. (A-B), (C-D), (A-C), (B-C)

D. (A-B), (C-D), (A-C)

Solution

1. Step 1: Sort edges by weight

   Edges sorted: (A-B:1), (C-D:2), (A-C:3), (B-C:4).

2. Step 2: Add edges without creating cycles

   Add (A-B), then (C-D). Adding (A-C) connects A and C without cycle. Adding (B-C) would create a cycle, so skip it.

3. Final Answer:

   (A-B), (C-D), (A-C) -> Option D

4. Quick Check:

   Edges chosen = smallest weights without cycles [OK]

Hint: Pick edges from smallest weight, skip if cycle forms [OK]

Common Mistakes:

• Including all edges regardless of cycles
• Choosing heavier edges before lighter ones
• Not checking for cycles before adding edges

4. In Kruskal's algorithm, what is the common error if the algorithm adds an edge that creates a cycle?

medium

A. The disjoint set structure is not used or updated correctly

B. Edges are not sorted by weight

C. Vertices are not labeled properly

D. The graph is directed instead of undirected

Solution

1. Step 1: Understand cycle prevention in Kruskal's

   Kruskal's algorithm uses a disjoint set (union-find) data structure to track connected components and avoid cycles.

2. Step 2: Identify the cause of cycle creation

   If an edge creates a cycle, it means the disjoint set was not used or updated properly to detect that the two vertices are already connected.

3. Final Answer:

   The disjoint set structure is not used or updated correctly -> Option A

4. Quick Check:

   Cycle error = faulty disjoint set use [OK]

Hint: Use disjoint sets to detect cycles before adding edges [OK]

Common Mistakes:

• Ignoring disjoint set updates
• Assuming sorting fixes cycles
• Confusing graph direction with cycle detection

5. You have a graph with edges: (X-Y: 2), (Y-Z: 2), (X-Z: 3), (Z-W: 1), (W-X: 4). Using Kruskal's algorithm, which set of edges forms the minimum spanning tree?

hard

A. (Z-W), (X-Y), (Y-Z)

B. (X-Y), (Y-Z), (X-Z)

C. (Z-W), (X-Z), (W-X)

D. (Z-W), (X-Y), (Y-Z), (W-X)

Solution

1. Step 1: Sort edges by weight

   Edges sorted: (Z-W:1), (X-Y:2), (Y-Z:2), (X-Z:3), (W-X:4).

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

   Add (Z-W), then (X-Y), then (Y-Z). Now all vertices X, Y, Z, W are connected. Adding (W-X) or (X-Z) would create cycles, so skip them.

3. Final Answer:

   (Z-W), (X-Y), (Y-Z) -> Option A

4. Quick Check:

   Minimum spanning tree = edges with smallest weights connecting all nodes [OK]

Hint: Add smallest edges until all vertices connected, avoid cycles [OK]

Common Mistakes:

• Adding extra edges causing cycles
• Skipping necessary edges to connect all vertices
• Choosing heavier edges before lighter ones