Maths - D1

?

D1- Chap 1 - 1.2 Krushkal's Algorithm

Krushkal's Algorithm

To find a minimum spanning tree for a network with n edges.

1. Choose the unused edge with the lowest value.

2. Add this edge to your tree.

3. If there are n-1 edges in your tree, stop. If not, go to step 1. 

1 of 4

D1- Chap 1 - 1.3 Prim's Algorithm

Prim's Algorithm 

1. From the specifed start vertex, draw the edge with the lowest vakue to start your tree. 

2. From any vertex in your minimum spanning tree, add the edge with the lowest value.

3. if there are n-1 edges in your tree, you have finished. If not go to step 2. 

2 of 4

D1- Chap 1 - 1.4 Comparison of Krushkal's and Prim

Whenever either Krushkal's or Prim's algorithm is applied to a network the resultant MST (Minimum Spanning Tree) is the same. However the order in which the edges were added the MST will differ. 

For this reason it is vital that when following one of the alogrithms the order in which you select the edges is clearly recorded. 

If the examiner can't clearly see you have used the algorithm specified then you will not get the marks.

3 of 4

D1- Chap 1 - 1.5 Matrix form of Prim;s algorithm

How to find a minimum spanning tree if the information is in a matrix?

1. Label the column corresponding to the start vertex with a 1. Delete the row correspondign to that vertex. 

2. Ring the smallest value in any labeled column. 

3. Label the column corresponding to the ringed vetext with a 2, etc. Delete the row corresponding to that vertex. 

4. Repeat steps 2 and 3 until all the rows have been deleted. 

5. Wirte down the oder in which the edges were selected (it is advised to do this as you go) and calculate the length of the MST. 

4 of 4

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Minimum Spanning Trees resources »