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.