Minimum Spanning Tree Kruskal's Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree is a subset of edges in a connected, weighted graph that connects all vertices together without any cycles and with the minimum possible total edge weight.

beginner

What is the main idea behind Kruskal's Algorithm?

Kruskal's Algorithm builds the MST by sorting all edges by weight and adding the smallest edge to the MST if it does not form a cycle, repeating until all vertices are connected.

intermediate

Why do we use a Disjoint Set (Union-Find) data structure in Kruskal's Algorithm?

The Disjoint Set helps efficiently check if adding an edge will create a cycle by tracking which vertices are in the same connected component.

intermediate

What is the time complexity of Kruskal's Algorithm?

The time complexity is O(E log E), where E is the number of edges, mainly due to sorting the edges. Union-Find operations are almost constant time.

beginner

In Kruskal's Algorithm, what happens if an edge connects two vertices already in the same set?

The edge is skipped to avoid creating a cycle in the MST.

What is the first step in Kruskal's Algorithm?

A Remove all cycles

B Pick any vertex as starting point

C Create adjacency matrix

D Sort all edges by weight

Kruskal's Algorithm starts by sorting all edges from smallest to largest weight.

Which data structure is commonly used to detect cycles in Kruskal's Algorithm?

A Disjoint Set (Union-Find)

B Queue

C Stack

D Binary Search Tree

Disjoint Set (Union-Find) efficiently tracks connected components to detect cycles.

What does Kruskal's Algorithm guarantee about the resulting tree?

A It contains all edges of the graph

B It has the maximum total edge weight

C It connects all vertices with minimum total edge weight

D It is a directed tree

Kruskal's Algorithm finds a tree connecting all vertices with the smallest total edge weight.

If adding an edge creates a cycle, what does Kruskal's Algorithm do?

A Skips the edge

B Adds the edge anyway

C Removes the cycle edges

D Restarts the algorithm

To keep the MST cycle-free, edges that create cycles are skipped.

What is the main factor affecting Kruskal's Algorithm's running time?

A Number of vertices

B Number of edges and sorting them

C Depth of recursion

D Size of adjacency list

Sorting edges by weight dominates the running time, which is O(E log E).

Explain step-by-step how Kruskal's Algorithm builds a Minimum Spanning Tree.

Think about sorting edges and using sets to avoid cycles.

Describe how the Disjoint Set (Union-Find) data structure helps in Kruskal's Algorithm.

Focus on cycle detection and set merging.

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