Kruskal's Algorithm (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 does Kruskal's algorithm find in a connected, weighted graph?
What does Kruskal's algorithm find in a connected, weighted graph?
A minimum spanning tree
In which order should edges be sorted in Kruskal's algorithm?
In which order should edges be sorted in Kruskal's algorithm?
Ascending order of weights
How many edges are in the MST for a graph with vertices?
How many edges are in the MST for a graph with vertices?
edges
What should the MST be initialised with at the start of Kruskal's algorithm?
What should the MST be initialised with at the start of Kruskal's algorithm?
An empty set of edges
Which method is used to check for cycles in Kruskal's algorithm?
Which method is used to check for cycles in Kruskal's algorithm?
Disjoint sets (union-find)
What is the time complexity of sorting edges in Kruskal's algorithm?
What is the time complexity of sorting edges in Kruskal's algorithm?
What is the space complexity of union-find structures in Kruskal's algorithm?
What is the space complexity of union-find structures in Kruskal's algorithm?
For what type of graph does Kruskal's algorithm work?
For what type of graph does Kruskal's algorithm work?
Connected graphs only
When is an MST unique in Kruskal's algorithm?
When is an MST unique in Kruskal's algorithm?
When edge weights are distinct
When should you stop adding edges in Kruskal's algorithm?
When should you stop adding edges in Kruskal's algorithm?
After edges are included