Constructing a Minimum Spanning Tree using Kruskal’s Algorithm

00:00 4 marks

Describe the steps of Kruskal’s algorithm to construct a minimum spanning tree (MST) for a given connected weighted graph. Your description should clearly outline how to select edges in ascending order of weight and ensure that no cycles are formed during the process.

Hint Hint

Hint

When considering an edge, ensure it connects two vertices that are not already in the same connected component to avoid creating a cycle.

Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Examiner Tips Examiner Tips
Common Errors Common Errors
Real World Context Real World Context
Focus Focus
Formula Booklet

Answer Answer

Complete Answer

To apply Kruskal’s algorithm, first sort all edges by weight in ascending order. Then, iterate through the sorted edges, adding each edge to the MST if it does not create a cycle. Continue this process until all vertices are connected, which will form the MST.

Mark Scheme Mark Scheme

Answer Explanation Answer Explanation

Examiner Tips Examiner Tips

Common Errors Common Errors

Focus Focus

Formula Booklet