Minimum Spanning Trees (Kruskal & Prim Algorithms) (Leaving Cert Applied Maths): Quizzes
📚Quizzes
Practise the questions
12 questions from this quiz
ShowHide
Practise the questions
12 questions from this quiz
For a graph with vertices, how many edges does a minimum spanning tree always have?
For a graph with vertices, how many edges does a minimum spanning tree always have?
edges
What is the main goal of finding a minimum spanning tree?
What is the main goal of finding a minimum spanning tree?
Cheapest way to connect all points
Which property must a minimum spanning tree NOT have?
Which property must a minimum spanning tree NOT have?
Cycles
What is the first step in Kruskal's algorithm?
What is the first step in Kruskal's algorithm?
List edges in ascending order by weight
How does Kruskal's algorithm consider edges?
How does Kruskal's algorithm consider edges?
Global approach - all edges at once
Can Prim's algorithm start from any vertex?
Can Prim's algorithm start from any vertex?
Yes, any vertex gives same MST
Which type of graph is Kruskal's algorithm particularly good for?
Which type of graph is Kruskal's algorithm particularly good for?
Sparse graphs with few edges
Which type of graph is Prim's algorithm particularly good for?
Which type of graph is Prim's algorithm particularly good for?
Dense graphs with many edges
What type of algorithms are both Kruskal's and Prim's algorithms?
What type of algorithms are both Kruskal's and Prim's algorithms?
Greedy algorithms
When all edge weights are distinct, what can we say about the MST?
When all edge weights are distinct, what can we say about the MST?
It is unique
If 185 km of cable costs €10,000 per km, what is the total cost?
If 185 km of cable costs €10,000 per km, what is the total cost?
€1,850,000
In Kruskal's algorithm, when should you skip an edge?
In Kruskal's algorithm, when should you skip an edge?
When it would create a cycle