Constructing Minimum Spanning Tree Using Kruskal’s Algorithm

00:00 7 marks

A connected weighted graph has five vertices labeled A, B, C, D, and E, with the following edges and weights:

– A-B: 2
– A-C: 3
– B-C: 1
– B-D: 4
– C-D: 5
– C-E: 6
– D-E: 7

Using Kruskal’s Algorithm, construct the Minimum Spanning Tree (MST) for this graph. Follow these steps:

(a) Sort the edges in non-decreasing order by weight.

(b) Apply the algorithm step-by-step by adding the smallest edge that does not form a cycle until the MST is complete.

Part a

4 minutes 3 marks

Question

Sort the given edges in non-decreasing order by weight. List the sorted order of the edges.

Hint Hint

Hint

Arrange edges starting from the smallest weight and list them in order.

Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Formula Booklet

Answer Answer

Complete Answer

B-C (1), A-B (2), A-C (3), B-D (4), C-D (5), C-E (6), D-E (7)

Mark Scheme Mark Scheme

Answer Explanation Answer Explanation

Formula Booklet

Part b

6 minutes 4 marks

Question

Using the sorted edge list from part (a), apply Kruskal’s Algorithm step-by-step to determine the edges included in the MST. Identify and skip any edge that would create a cycle. List the edges of the MST.

Hint Hint

Hint

At each step, consider the sorted edges and check if adding the current edge connects two vertices that are already in the same connected component. If so, adding the edge will create a cycle and should be skipped.

Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Formula Booklet

Answer Answer

Complete Answer

Edges in MST: B-C, A-B, B-D, C-E.

Mark Scheme Mark Scheme

Answer Explanation Answer Explanation

Formula Booklet