# Further Maths - Kruskal's Algorithm

> Source: https://ollybritton.com/notes/a-level/further-maths/topics/kruskals/ · Updated: 2021-11-07 · Tags: school, further-maths, decision

## See Also
- [Further Maths - Graphs](https://ollybritton.com/notes/a-level/further-maths/topics/graphs/)
- [Further Maths - Prim's Algorithm](https://ollybritton.com/notes/a-level/further-maths/topics/prims/)

## Flashcards
##### What is a spanning tree??
A tree that includes all the vertices of a graph.

##### What is a minimum spanning tree??
A tree that includes all the vertices of a graph at the minimum possible cost.

##### 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.

##### How many edges do you need to create a minimum spanning tree for $7$ vertices??
$$
6
$$

##### How many edges do you need to create a minimum spanning tree for $69$ vertices??
$$
68
$$

##### 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.

##### What is the complexity of Kruskal's algorithm??
$$
O(n^3)
$$

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt