3. Algorithms on Graphs

Question 1

Define the term MST (Minimum Spanning Tree)

Answer 1

A spanning tree such that the total length of its arc is as small as possible

Question 2

Name the 2 algorithms used to find the MST

Answer 2

1. Kruskal’s algorithm

2. Prim’s algorithm

Question 3

What are the steps to Kruskal’s algorithm?

Answer 3

1. Sort arcs into ascending order of weight
2. Select arc of least weight to start the tree
3. Consider the next arc of least weight
4. If the arc forms a cycle, reject it
5. If it does not, add it to the tree
6. Repeat steps 3-5 until all vertices are added

Question 4

What are the steps to Prim’s algorithm?

Answer 4

1. Choose any vertex to start tree.
2. Select an arc of least weight that joins a vertex already in the tree to a vertex that is not
3. Repeat step 2 until all vertices are added

Question 5

What are the steps to Prim’s algorithm in a distance matrix?

Answer 5

1. Choose any vertex to start the tree
2. Delete row in matrix of chosen vertex
3. Number the column in matrix for chosen vertex
4. Put a ring around the lowest undeleted entry in the numbered columns
5. Ringed entry becomes next arc to be added to tree
6. Repeat steps 2-5 until all rows have been deleted

Question 6

What is Dijkstra’s algorithm used for?

Answer 6

Finding the shortest route between two vertices

Question 7

What are the steps to Dijkstra’s algorithm?

Answer 7

1. Label start vertex S with a final label 0
2. Record a working value for each vertex that is directly connected to the vertex that just received a label
3. Look at working values of all values with no final label and select the smallest one which becomes the final label for that vertex
4. Repeat steps 2-3 until destination vertex receives its final label
5. To find the shortest path, trace back from the destination vertex to the start vertex where the final labels subtracted equal the weight of the arc