Minimum Spanning Trees (Kruskal & Prim Algorithms) (Leaving Cert Applied Maths): Flashcards
📚Flashcards
Practise the cards
13 cards from this deck
ShowHide
Practise the cards
13 cards from this deck
What is a minimum spanning tree (MST)?
What is a minimum spanning tree (MST)?
Connects all vertices w/ smallest total edge weight
No. of edges in MST with vertices
No. of edges in MST with vertices
edges
MST cycle property
MST cycle property
Contains no cycles
Kruskal's algorithm approach
Kruskal's algorithm approach
Considers edges in ascending weight order, avoids cycles
Kruskal's first step
Kruskal's first step
List all edges in ascending order of weight
Kruskal's & Prim's algorithm type
Kruskal's & Prim's algorithm type
Greedy algorithms
Prim's algorithm approach
Prim's algorithm approach
Grows tree from starting vertex, adds cheapest edge to new vertex
Prim's starting vertex flexibility
Prim's starting vertex flexibility
Can start from any vertex
Kruskal's approach (global/local)
Kruskal's approach (global/local)
Global - considers all edges at once
Prim's approach (global/local)
Prim's approach (global/local)
Local - grows from one starting point
When is an MST unique?
When is an MST unique?
When all edge weights are distinct
Kruskal's cycle detection rule
Kruskal's cycle detection rule
Skip if both vertices already connected
Best graph type for Kruskal's
Best graph type for Kruskal's
Sparse graphs (few edges)