 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/functional-programming-design-and-analysis-of-algorithms/7/b/solution

Write each undirected edge with its smaller endpoint first. Kruskal's algorithm orders candidates first by weight and then lexicographically:

edge (4, 6) (1, 3) (3, 4) (1, 4) (4, 5) (5, 6) (1, 2) weight 1223334 action add add add reject: closes a cycle add reject: closes a cycle add and finish

Thus the requested addition order is

(4, 6), (1, 3), (3, 4), (4, 5), (1, 2),

and the minimum spanning tree has total weight $12$ . Five accepted edges connect all six vertices, so the remaining weight-four edges need not be scanned.

 New to topics? Read the docs here!