Prims pt-2
Prims algorithm using a matrix:
1. choose any vertex to start the tree (in an exam you will likely be told which vertex to start with)
2. delete the row in the matrix for the chosen vertex
3. Number the column in the matrix for the chosen vertex
4. put a box around the lowest undeleted entry in the numbered columns (if there is an equal choice, choose
randomly)
5. the ringed entry becomes the next arc to be added to the tree
6. repeat steps 2,3,4 and 5 untill all rows are deleted
A B C D E
A - 27 12 23 74
B 27 - 47 15 71
C 12 47 - 28 87
D 23 15 28 - 75
E 74 71 87 75 -
Prims algorithm using a matrix:
1. choose any vertex to start the tree (in an exam you will likely be told which vertex to start with)
2. delete the row in the matrix for the chosen vertex
3. Number the column in the matrix for the chosen vertex
4. put a box around the lowest undeleted entry in the numbered columns (if there is an equal choice, choose
randomly)
5. the ringed entry becomes the next arc to be added to the tree
6. repeat steps 2,3,4 and 5 untill all rows are deleted
A B C D E
A - 27 12 23 74
B 27 - 47 15 71
C 12 47 - 28 87
D 23 15 28 - 75
E 74 71 87 75 -
