Implement Kruskal's and Prim's MSTStep 3 of 5

Kruskal's Chosen Edges

12345

Step 3: Kruskal's Chosen Edges

Knowing the MST's cost is useful, but a network engineer also needs the actual list of cables to lay. Extend Kruskal's algorithm to return the chosen edges themselves.

Implement kruskal_edges(n, edges):

  • Process edges in deterministic sorted order, tie-breaking by (weight, u, v).
  • Return the list of selected edges as (u, v, weight) tuples, in the order they were chosen.

Because the tie-break is fully determined by (weight, u, v), the output is reproducible for any input.

Real use: this is the concrete build plan, exactly which links to install, cheapest-first.

Hints
Starter code
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


def kruskal(n, edges):
    dsu = DSU(n)
    total = 0
    for w, u, v in sorted((w, u, v) for (u, v, w) in edges):
        if dsu.union(u, v):
            total += w
    return total


def kruskal_edges(n, edges):
    """Return the list of (u, v, weight) edges chosen for the MST, deterministically."""
    # TODO: sort by (weight, u, v); collect edges whose union succeeds
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step