>>> kruskal(4, [(0, 1, 3), (1, 2, 5), (2, 3, 1)]) [(2, 3, 1), (0, 1, 3), (1, 2, 5)] >>> kruskal(4, [(0, 1, 3), (1, 2, 5), (2, 3, 1), (0, 2, 1), (0, 3, 2)]) [(2, 3, 1), (0, 2, 1), (0, 1, 3)] >>> kruskal(4, [(0, 1, 3), (1, 2, 5), (2, 3, 1), (0, 2, 1), (0, 3, 2), ... (2, 1, 1
(
num_nodes: int, edges: list[tuple[int, int, int]]
)
| 1 | def kruskal( |
| 2 | num_nodes: int, edges: list[tuple[int, int, int]] |
| 3 | ) -> list[tuple[int, int, int]]: |
| 4 | """ |
| 5 | >>> kruskal(4, [(0, 1, 3), (1, 2, 5), (2, 3, 1)]) |
| 6 | [(2, 3, 1), (0, 1, 3), (1, 2, 5)] |
| 7 | |
| 8 | >>> kruskal(4, [(0, 1, 3), (1, 2, 5), (2, 3, 1), (0, 2, 1), (0, 3, 2)]) |
| 9 | [(2, 3, 1), (0, 2, 1), (0, 1, 3)] |
| 10 | |
| 11 | >>> kruskal(4, [(0, 1, 3), (1, 2, 5), (2, 3, 1), (0, 2, 1), (0, 3, 2), |
| 12 | ... (2, 1, 1)]) |
| 13 | [(2, 3, 1), (0, 2, 1), (2, 1, 1)] |
| 14 | """ |
| 15 | edges = sorted(edges, key=lambda edge: edge[2]) |
| 16 | |
| 17 | parent = list(range(num_nodes)) |
| 18 | |
| 19 | def find_parent(i): |
| 20 | if i != parent[i]: |
| 21 | parent[i] = find_parent(parent[i]) |
| 22 | return parent[i] |
| 23 | |
| 24 | minimum_spanning_tree_cost = 0 |
| 25 | minimum_spanning_tree = [] |
| 26 | |
| 27 | for edge in edges: |
| 28 | parent_a = find_parent(edge[0]) |
| 29 | parent_b = find_parent(edge[1]) |
| 30 | if parent_a != parent_b: |
| 31 | minimum_spanning_tree_cost += edge[2] |
| 32 | minimum_spanning_tree.append(edge) |
| 33 | parent[parent_a] = parent_b |
| 34 | |
| 35 | return minimum_spanning_tree |
| 36 | |
| 37 | |
| 38 | if __name__ == "__main__": # pragma: no cover |