 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/functional-programming-design-and-analysis-of-algorithms/8/c/solution

Run Kruskal's algorithm in nonincreasing order of edge weight, accepting an edge exactly when its endpoints belong to different current connected components. Use a disjoint-set data structure to test and merge those components. Stop after accepting

∣ V ∣ - 1

Equivalently, apply ordinary Kruskal's algorithm to

w^{'} (e) = - w (e)

e \in T \sum w^{'} (e) = - e \in T \sum w (e),

so minimizing transformed total weight is exactly maximizing original total weight. Thus the output is a maximum spanning tree. Equal weights may be processed in any fixed order. Sorting dominates the time complexity, giving

O (∣ E ∣ lo g ∣ E ∣ + ∣ V ∣)

 New to topics? Read the docs here!