Minimum Spanning Tree Kruskal's Algorithm in DSA C - 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

↓

Are all vertices connected?

↓

Done

Kruskal's algorithm sorts edges by weight, then adds edges one by one to the MST if they don't form a cycle, until all vertices are connected.

Execution Sample

DSA C

Edges = [(A-B,1), (B-C,3), (A-C,2), (C-D,4)]
Sort edges by weight
Initialize MST = {}
For each edge in sorted order:
  If edge does not form cycle:
    Add edge to MST
Return MST

This code builds a minimum spanning tree by adding edges from smallest to largest weight without creating cycles.

Execution Table

Step	Operation	Edge Considered	Cycle Check Result	MST Edges	Visual State
1	Sort edges by weight	-	-	{}	No edges yet
2	Consider edge	A-B (1)	No cycle	{A-B}	A--B
3	Consider edge	A-C (2)	No cycle	{A-B, A-C}	A--B | C
4	Consider edge	B-C (3)	Forms cycle	{A-B, A-C}	A--B | C
5	Consider edge	C-D (4)	No cycle	{A-B, A-C, C-D}	A--B | C--D
6	Check if MST complete	-	Yes	{A-B, A-C, C-D}	All vertices connected
7	Done	-	-	{A-B, A-C, C-D}	Final MST

💡 All vertices connected, MST complete with edges A-B, A-C, C-D

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}
Edges Considered	[]	[A-B]	[A-B, A-C]	[A-B, A-C, B-C]	[A-B, A-C, B-C, C-D]	[A-B, A-C, B-C, C-D]
Connected Components	4 (A,B,C,D separate)	3 (A-B connected)	2 (A-B-C connected)	2 (no change, B-C edge discarded)	1 (all connected)	1 (all connected)

Key Moments - 3 Insights

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

Because adding edge B-C would create a cycle with edges A-B and A-C already in MST, as shown in step 4 of the execution_table where cycle check result is 'Forms cycle'.

How do we know when the MST is complete?

When all vertices are connected in a single component, meaning the number of connected components is 1, as shown after step 5 in variable_tracker and confirmed in step 6 of execution_table.

Why do we sort edges by weight at the start?

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

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the cycle check result for edge B-C (3)?

A No cycle

B Forms cycle

C Edge not considered

D Edge added to MST

💡 Hint

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

At which step does the MST become complete with all vertices connected?

A Step 6

B Step 5

C Step 3

D Step 7

💡 Hint

Look at the 'Check if MST complete' operation and connected components in variable_tracker

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

A MST would have fewer edges but still connect all vertices

B MST would include edge B-C (3) instead

C MST would be incomplete, some vertices disconnected

D No change, MST remains the same

💡 Hint

Refer to the visual state and connected components after step 5 in variable_tracker

Concept Snapshot

Kruskal's Algorithm builds MST by:
- Sorting edges by weight
- Adding edges from smallest to largest
- Skipping edges that form cycles
- Stopping when all vertices connect
Uses Union-Find or similar to detect cycles

Full Transcript

Kruskal's algorithm starts by sorting all edges by their weight. It then picks the smallest edge and checks if adding it creates a cycle in the growing MST. If no cycle forms, the edge is added. If a cycle would form, the edge is discarded. This process repeats until all vertices are connected in one component, forming the minimum spanning tree. The execution table shows each step with edges considered, cycle checks, and the MST's state. The variable tracker follows MST edges and connected components count. Key moments clarify why edges causing cycles are skipped and how completion is detected. The visual quiz tests understanding of cycle detection, MST completion, and effects of missing edges.

Practice

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

easy

A. To sort the vertices of a graph

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To find the minimum spanning tree 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 algorithms

   Unlike shortest path or cycle detection, Kruskal's focuses on building a minimum spanning tree.

3. Final Answer:

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

4. Quick Check:

   Kruskal's algorithm = Minimum Spanning Tree [OK]

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

Common Mistakes:

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

2. Which data structure is commonly used in Kruskal's algorithm to detect cycles efficiently?

easy

A. Disjoint Set (Union-Find)

B. Stack

C. Queue

D. Priority Queue

Solution

1. Step 1: Identify cycle detection method in Kruskal's

   Kruskal's algorithm uses a Disjoint Set (Union-Find) data structure to check if adding an edge creates a cycle by checking if two vertices belong to the same set.

2. Step 2: Compare other data structures

   Queue and stack do not help detect cycles efficiently here; priority queue is used for sorting edges but not cycle detection.

3. Final Answer:

   Disjoint Set (Union-Find) -> Option A

4. Quick Check:

   Cycle detection in Kruskal's = Union-Find [OK]

Hint: Use Union-Find to quickly check cycles in Kruskal's [OK]

Common Mistakes:

• Confusing priority queue with cycle detection
• Using stack or queue for cycle detection
• Not knowing Union-Find purpose

3. Consider the following edges of a graph with weights:
Edges = [(A-B, 1), (B-C, 4), (A-C, 3), (C-D, 2)]
What is the total weight of the minimum spanning tree found by Kruskal's algorithm?

medium

A. 7

B. 6

C. 8

D. 10

Solution

1. Step 1: Sort edges by weight

   Sorted edges: (A-B,1), (C-D,2), (A-C,3), (B-C,4)

2. Step 2: Pick edges without cycles

   Pick (A-B,1), then (C-D,2), then (A-C,3). Adding (B-C,4) creates a cycle, so skip it.

3. Step 3: Calculate total weight

   Total weight = 1 + 2 + 3 = 6

4. Final Answer:

   6 -> Option B

5. Quick Check:

   Sum of MST edges = 6 [OK]

Hint: Sort edges, pick smallest without cycle until all connected [OK]

Common Mistakes:

• Adding all edges without checking cycles
• Choosing edges in wrong order
• Miscounting total weight

4. The following C code snippet is part of Kruskal's algorithm. What is the error?

int findParent(int parent[], int i) {
    if (parent[i] == i)
        return i;
    return findParent(parent, parent[i]);
}

void unionSet(int parent[], int x, int y) {
    int xset = findParent(parent, x);
    int yset = findParent(parent, y);
    parent[xset] = yset;
}

medium

A. unionSet should swap xset and yset

B. unionSet should not change parent array

C. Missing path compression in findParent

D. findParent should return void

Solution

1. Step 1: Analyze findParent function

   findParent recursively finds the root parent but does not update parent[i] to root, missing path compression optimization.

2. Step 2: Understand unionSet function

   unionSet correctly merges sets by updating parent of one root to another; no swap needed.

3. Final Answer:

   Missing path compression in findParent -> Option C

4. Quick Check:

   Path compression missing = findParent optimization [OK]

Hint: Add path compression to speed up findParent [OK]

Common Mistakes:

• Thinking unionSet must swap parents
• Believing findParent should return void
• Ignoring path compression importance

5. Given a graph with vertices {1, 2, 3, 4} and edges with weights:
(1-2, 5), (1-3, 3), (2-3, 4), (2-4, 2), (3-4, 7)
Using Kruskal's algorithm, which edges will be included in the minimum spanning tree?

hard

A. (2-4), (1-3), (2-3)

B. (1-3), (2-4), (1-2)

C. (2-4), (1-3), (1-2)

D. (1-2), (2-3), (3-4)

Solution

1. Step 1: Sort edges by weight

   Sorted edges: (2-4,2), (1-3,3), (2-3,4), (1-2,5), (3-4,7)

2. Step 2: Pick edges without cycles

   Pick (2-4,2), then (1-3,3). Next (2-3,4) connects 2 and 3 which are in different sets, so pick it. After these three edges, all vertices are connected and MST is complete.

3. Step 3: Verify options

   (2-4), (1-3), (2-3) matches edges (2-4), (1-3), (2-3). (2-4), (1-3), (1-2) includes (1-2) which is heavier than (2-3), so incorrect.

4. Final Answer:

   (2-4), (1-3), (2-3) -> Option A

5. Quick Check:

   Pick smallest edges connecting all vertices without cycle [OK]

Hint: Sort edges, pick smallest connecting new vertices until all connected [OK]

Common Mistakes:

• Choosing heavier edges over lighter ones
• Adding edges that create cycles
• Not stopping after n-1 edges