Summary of Chapter 3

1 Kruskal's algorithm and Prim's algorithm can be used to find a minimum spanning tree, but they take different approaches.2 To use Kruskal's algorithm, you sort the arcs into ascending order of weight and use the arc of least weight to start the tree. You then add arcs in order of ascending weight, unless an arc would form a cycle, in which case it is rejected.3 To use Prim's algorithm, you choose any vertex to start the tree. You then select an arc of least weight that joins a vertex that is already in the tree to a vertex that is not yet in the tree. You repeat this until all vertices are connected.4 Prim's algorithm can be applied to a distance matrix. You choose any vertex to start the tree. You delete the row in the matrix for the chosen vertex and number the column in the matrix for the chose vertex. You ring the lowest undeleted entry in the labelled columns, which becomes the next vertex. You repeat this until all rows are deleted.5 You can use Dijkstra's algorithm to find the shortest path between two vertices in a network.6 The start vertex is given the final value 0. Every vertex that is directly connected to the start vertex is given a working value                   final value at start + weight of arc.   Select the smallest working value. This is the final value for that vertex. Repeat until the destination vertex receives its final label. Find the shortest path by tracing back from destination to start. Include an arc AB on the route if B is already on the route and                   final label B - final label A = weight of arc AB7 Each vertex is replaced by a box

Page 1