Further Maths - Kruskal's Algorithm
Pearson Edexcel Further Mathematics 2022
See Also
Flashcards
Spanning trees
What is a minimum spanning tree?
A tree that includes all the vertices of a graph at the minimum possible cost.
The steps of Kruskal’s algorithm
What is the first step of Kruskal’s algorithm?
List the edges in the order of weight, smallest first.
What step comes after listing out the edges of a graph in weight order for Kruskal’s algorithm?
Repeatedly choosing the edge with the smallest weight as long as it does not form a with already chosen edges.
Counting edges in a minimum spanning tree
How many edges do you need to create a minimum spanning tree for $7$ vertices?
How many edges do you need to create a minimum spanning tree for $69$ vertices?
Greedy algorithms and complexity
What is a greedy algorithm?
One that makes locally optimal choices without considering the context.
Why is Kruskal’s algorithm greedy?
Because it chooses the best edge available at every stage.