See Also
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) $$
Backlinks
Metadata
date: 2021-11-07 15:17
tags:
- '@?public'
- '@?school'
- '@?further-maths'
- '@?decision'
title: Further Maths - Kruskal's Algorithm