Interactive practice questions
Apply Prim’s algorithm to the following network:
Starting from vertex $A$A, which edge should be selected first?
$AB$AB
$AC$AC
$AD$AD
$BC$BC
$BD$BD
$CD$CD
Which edge should be selected second?
$AB$AB
$AC$AC
$AD$AD
$BC$BC
$BD$BD
$CD$CD
Which edge should be selected third?
$AB$AB
$AC$AC
$AD$AD
$BC$BC
$BD$BD
$CD$CD
What is the weight of the minimal spanning tree?
Apply Kruskal’s algorithm to the following network:
The following weighted network shows possible connections (and associated costs, in millions of dollars) for connecting rural towns to a common cabled internet service.
To minimise the cost of connecting each town to the network, we want to find the minimal spanning tree.
The direct flight routes between five major cities are shown in the network below. Each edge is marked with the distance (in km) traveled on each route.
The operating airline wants to find the minimal spanning tree for the network to maximise efficiency.