How Kruskal's Algorithm Works

Two lines set up the entire algorithm. Line 15 sorts the edge list in ascending order by weight using a lambda that extracts the third element of each tuple. The sort is in-place on the local variable, so the input list is not mutated. After sorting, greedy selection by weight is correct because of the MST cut property: for any partition of the vertices into two groups, the minimum-weight edge crossing the partition must appear in at least one MST. Processing edges cheapest-first and skipping cycle-forming ones finds that edge at the right moment. Line 17 initializes the union-find structure: list(range(num_nodes)) creates a list where parent[i] = i for every node, encoding that each node is its own root and no two nodes are yet connected. The entire disjoint-set forest is this single list.

find_parent is a closure over the parent list defined in the enclosing scope. It finds the root of node i's component by following parent pointers until it reaches a node that is its own parent (i == parent[i]). The path-compression step on line 21 is the optimization that makes union-find near-linear over many operations: after the recursive call returns the root, the current node's parent pointer is updated to point directly to the root. On the next call for any node in this path, the lookup reaches the root in one step instead of following the whole chain. Without path compression, a degenerate series of unions could produce a chain of length n, making each lookup O(n). With it, the amortized cost approaches O(alpha(n)), where alpha is the inverse Ackermann function, effectively constant for any practical n.

The greedy loop processes sorted edges and makes an accept-or-reject decision for each one. Lines 28 and 29 find the root of both endpoints. If parent_a == parent_b, both endpoints are in the same component; adding the edge would create a cycle, so the algorithm skips it. If the roots differ, the edge connects two separate components and is safe to add. Line 31 accumulates the total MST cost. Line 32 records the edge in the result list. Line 33 performs the union by setting parent[parent_a] = parent_b, making one root point to the other. This is union-by-root without rank tracking; pathological union sequences can produce unbalanced trees. Path compression in find_parent compensates by flattening trees dynamically.

The # pragma: no cover comment on line 38 tells the coverage tool to skip the __main__ block during test collection. The block reads the node and edge counts on a single line, then reads each edge as three space-separated integers on its own line. Line 43 uses a generator expression with int(x) to convert the tokens rather than a list comprehension with explicit indexing, which is the style the repository favors for small, readable conversions. The result of kruskal on line 46 is discarded rather than printed, which matches the pattern from the bellman_ford __main__ block: the caller is expected to use print_distance or equivalent for output. Unlike graphs/bellman_ford.py, this file does not call doctest.testmod() in the __main__ block, so the three doctests in the function are only exercised by CI, not by direct invocation.