Minimum Spanning Trees Flashcards
1
Q
What is a Minimum Spanning Tree?
A
A Minimum Spanning Tree:
- connects all nodes
- minimises the weight of the edges
2
Q
How does the Greedy Algorithm for creating Minimum Spanning Trees work?
A
Begin with A = empty_set
while A is not an MST:
find a safe edge E for A add E to A
3
Q
What is the complexity of Kruskal’s Algorithm?
A
O( E * log(V) )
4
Q
What is the complexity of Prim’s Algorithm?
A
O( E + V * log(V) )
