Chapter 3

Question 1

Kruskal’s algorithm

Answer 1

1) Sort arcs by weight
2) Start with arc of lowest weight
3) Add arcs in order of ascending weight (unless forming a cycle)

Question 2

Prim’s algorithm

Answer 2

1) Choose any vertex
2) Select an arc of least weight that joins a vertex that is in the tree to one that is not
3) stop when all vertices are connected

Question 3

Prim’s algorithm on a distance matrix

Answer 3

1) Choose any vertex
2) Number the column of the chosen vertex and delete its row
3) Ring the lowest undeleted entry in the labeled columns, which becomes the next vertex
4) Repeat until all vertices are connected