Comparing MST Algorithms (Edexcel A-Level Further Mathematics): Quizzes
📚Quizzes
Practise the questions
10 questions from this quiz
ShowHide
Practise the questions
10 questions from this quiz
What is a minimum spanning tree (MST)?
What is a minimum spanning tree (MST)?
A subset of edges connecting all vertices with minimum weight and no cycles
Which property must an MST always have?
Which property must an MST always have?
No cycles
Which is a typical application of MSTs?
Which is a typical application of MSTs?
Optimising electrical grids
How does Prim's algorithm build an MST?
How does Prim's algorithm build an MST?
Grows from a single vertex
What is Kruskal's algorithm's approach?
What is Kruskal's algorithm's approach?
Adds smallest edges, ensuring no cycles
Which graph representation works well with Prim's algorithm?
Which graph representation works well with Prim's algorithm?
Adjacency matrices
Which representation suits Kruskal's algorithm?
Which representation suits Kruskal's algorithm?
Edge lists
What is Prim's time complexity using a matrix?
What is Prim's time complexity using a matrix?
What is Kruskal's algorithm's time complexity?
What is Kruskal's algorithm's time complexity?
How does Kruskal's detect cycles?
How does Kruskal's detect cycles?
Explicitly using disjoint sets