AQA D1 Minimum Spanning Trees

1. Select the arc with the lowest weight and highlight it on the graph

2. Keep a track of the arcs selected in a list (with weight)

3. Select and highlight the next lowest wight arc anywhere on the graph

4. Repeat step 3 until all the nodes are in the tree

5. Do not select an arc if it forms a cycle

No. OF ARCS IN MST= n-1

ARCS SHOULD BE LISTED IN ASCENDING ORDER

1. Select the lowest weight arc out of the given start vertex/ select the lowest weight arc

2. Highlight the arc and keep a list of all the arcs selected (and their weight)

3. Select the lowest weight arc connected to one of the nodes already in the MST

4. Repeat step 3 until all nodes are connected, ignore any arcs that make a cycle

No. OF ARCS IN MST= n-1

1. Cross out the row of the given start vertex/ select any vertex if it is not given

2. Circle the start vertex in the very top row

3. Select the smallest number below the selected vertex and circle it

4. Cross out the row and circle the vertex in the top row

5. Select the smallest number below any of the circled vertices

6. Repeat step 4 until all the rows are crossed out