Minimum Spanning Tree Kruskal's Algorithm in DSA Java - 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 them one by one to the MST, skipping edges that would form a cycle, 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 already connected, allowing quick union and find operations.

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 edges. Union-Find operations are almost constant time.

advanced

What happens if the graph is not connected when running Kruskal's Algorithm?

Kruskal's Algorithm will find a Minimum Spanning Forest, which is a set of MSTs for each connected component, since it cannot connect all vertices in a disconnected graph.

What is the first step in Kruskal's Algorithm?

A Sort all edges by their weight

B Pick any vertex as the starting point

C Create adjacency list

D Remove all cycles from the graph

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 Stack

B Queue

C Disjoint Set (Union-Find)

D Binary Search Tree

Disjoint Set (Union-Find) efficiently detects cycles by tracking connected components.

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

A Adds the edge anyway

B Removes a vertex

C Restarts the algorithm

D Skips the edge

Kruskal's Algorithm skips edges that would create cycles to keep the MST valid.

What does Kruskal's Algorithm produce if the graph is disconnected?

A Minimum Spanning Forest

B No output

C A single MST

D A cycle

It produces a Minimum Spanning Forest, which is MSTs for each connected part.

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

A Number of vertices

B Number of edges

C Number of cycles

D Number of connected components

Sorting edges by weight dominates the time complexity, which depends on the number of edges.

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

Think about sorting edges and checking cycles with Union-Find.

Describe how the Disjoint Set data structure helps in Kruskal's Algorithm.

Focus on cycle detection and efficient merging.

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