3 - Algorithms on graphs

Question 1

Give two algorithms used to find minimum spanning trees.

Answer 1

• Kruskals
• Prims

Question 2

Describe Kruskal’s algorithm

Answer 2

1. Sort all arcs into ascending order of weight
2. Select arc of least weight to start the tree
3. Consider the next arc of least weight
   * If it would form a cycle with the arcs already selected, reject it
   * If it does not form a cycle, add it to the tree
4. Repeat Step 3 until all vertices are connected

Question 3

Describe graphical Prim’s algorithm.

Answer 3

1. Choose any vertex
2. Select an arc of least weight that joins to a vertex not yet in the tree
3. Repeat Step 2 until all vertices are connected

Question 4

Describe tabular Prim’s algorithm.

Answer 4

1. Choose a vertex to start tree
2. Delete row in matrix for chosen vertex
3. Number column in matrix for chosen vertex
4. Put a ring around the smallest undeleted entry in numbered columns
5. Ringed entry becomes next arc
6. Repeat Steps 2,3,4 and 5 until all rows have been deleted

Question 4

Describe tabular Prim’s algorithm.

Answer 4

1. Choose a vertex to start tree
2. Delete row in matrix for chosen vertex
3. Number column in matrix for chosen vertex
4. Put a ring around the smallest undeleted entry in numbered columns
5. Ringed entry becomes next arc
6. Repeat Steps 2,3,4 and 5 until all rows have been deleted

Question 5

Describe Dijkstra’s algorithm.

Answer 5

1. Label start vertex with final label 0.
2. Record working value at each vertex directly connected to vertex just labelled (X).
   * Working value = Xvalue + arc length
   * Only replace a current working value if the new one would be smaller
3. Make smallest working value final label
4. Repeat Steps 2 and 3 until the targert vertex has a final label.
5. To find shortest, trace back from target vertex to start vertex.

Question 6

Describe Floyd’s algorithm

Answer 6

1. Set up initial route and distance tables. Route is just the column filled with that node, distance is the direct distance for the an arc between the nodes. (use infinity if there is none and a dash for self nodes)
2. Shade first row and column and copy these values/letters into the next tables
3. If the sum of shaded values is less, then replace, and change the letter to the iteration you are on (ie if 1st, then A, if 2nd then B)
4. Repeat Steps 2 and 3, moving across one column and down one row

• For n nodes, there are n iterations