Kruskal Selection Trace

Problem

Run Kruskal's algorithm and list the edges it selects, in selection order.

Sort edges by (weight, u, v) so ties are broken deterministically, then sweep with union-find and keep an edge only when it joins two different components. edges is an undirected [u, v, w] list. Return the chosen edges as [u, v] pairs; a disconnected graph simply yields fewer edges.

Hint

Sort by weight first, then add an edge only if union-find keeps the forest acyclic.

Test cases

case 1

in: [4,[[0,1,1],[1,2,2],[0,2,3],[2,3,4]]]

expected: [[0,1],[1,2],[2,3]]

case 2

in: [4,[[0,1,1],[2,3,1],[0,2,1]]]

expected: [[0,1],[0,2],[2,3]]

case 3

in: [3,[[0,1,5]]]

expected: [[0,1]]

case 4

in: [2,[]]

expected: []

case 5

in: [3,[[1,2,2],[0,1,2],[0,2,2]]]

expected: [[0,1],[0,2]]

Starter codePython

def kruskal_selection_trace(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor