Kruskal's Algorithm in Python, Java and TypeScript

def find(parent, vertex):
    while parent[vertex] != vertex:
        parent[vertex] = parent[parent[vertex]]
        vertex = parent[vertex]
    return vertex


def kruskal(vertices, edges):
    parent = {vertex: vertex for vertex in vertices}
    size = {vertex: 1 for vertex in vertices}
    tree, skipped = [], []
    for u, v, weight in sorted(edges, key=lambda edge: edge[2]):
        if len(tree) == len(vertices) - 1:
            break
        root_u, root_v = find(parent, u), find(parent, v)
        if root_u == root_v:
            skipped.append((u, v, weight))
            continue
        if size[root_u] < size[root_v]:
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        tree.append((u, v, weight))
    return tree, skipped


def label(edges):
    return ", ".join(f"{u}-{v} {weight}" for u, v, weight in edges)


VERTICES = ["A", "B", "C", "D", "E", "F"]
EDGES = [
    ("A", "B", 4), ("A", "C", 1), ("B", "C", 2), ("B", "D", 5), ("C", "D", 8),
    ("C", "E", 9), ("D", "E", 3), ("D", "F", 7), ("E", "F", 6),
]

tree, skipped = kruskal(VERTICES, EDGES)
print("tree:", label(tree))
print("skipped:", label(skipped))
print("total:", sum(weight for _, _, weight in tree))

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class KruskalCode {
    record Edge(String u, String v, int weight) {
        @Override
        public String toString() {
            return u + "-" + v + " " + weight;
        }
    }

    record Result(List<Edge> tree, List<Edge> skipped) {}

    static String find(Map<String, String> parent, String vertex) {
        while (!parent.get(vertex).equals(vertex)) {
            parent.put(vertex, parent.get(parent.get(vertex)));
            vertex = parent.get(vertex);
        }
        return vertex;
    }

    static Result kruskal(List<String> vertices, List<Edge> edges) {
        Map<String, String> parent = new HashMap<>();
        Map<String, Integer> size = new HashMap<>();
        for (String vertex : vertices) {
            parent.put(vertex, vertex);
            size.put(vertex, 1);
        }
        List<Edge> sorted = new ArrayList<>(edges);
        sorted.sort(Comparator.comparingInt(Edge::weight));
        List<Edge> tree = new ArrayList<>();
        List<Edge> skipped = new ArrayList<>();
        for (Edge edge : sorted) {
            if (tree.size() == vertices.size() - 1) break;
            String rootU = find(parent, edge.u());
            String rootV = find(parent, edge.v());
            if (rootU.equals(rootV)) {
                skipped.add(edge);
                continue;
            }
            if (size.get(rootU) < size.get(rootV)) {
                String swap = rootU;
                rootU = rootV;
                rootV = swap;
            }
            parent.put(rootV, rootU);
            size.put(rootU, size.get(rootU) + size.get(rootV));
            tree.add(edge);
        }
        return new Result(tree, skipped);
    }

    static String label(List<Edge> edges) {
        return edges.stream().map(Edge::toString).collect(Collectors.joining(", "));
    }

    public static void main(String[] args) {
        List<String> vertices = List.of("A", "B", "C", "D", "E", "F");
        List<Edge> edges = List.of(
            new Edge("A", "B", 4), new Edge("A", "C", 1), new Edge("B", "C", 2), new Edge("B", "D", 5), new Edge("C", "D", 8),
            new Edge("C", "E", 9), new Edge("D", "E", 3), new Edge("D", "F", 7), new Edge("E", "F", 6));
        Result result = kruskal(vertices, edges);
        System.out.println("tree: " + label(result.tree()));
        System.out.println("skipped: " + label(result.skipped()));
        System.out.println("total: " + result.tree().stream().mapToInt(Edge::weight).sum());
    }
}

type Edge = [string, string, number];

function find(parent: Map<string, string>, vertex: string): string {
  while (parent.get(vertex) !== vertex) {
    parent.set(vertex, parent.get(parent.get(vertex)!)!);
    vertex = parent.get(vertex)!;
  }
  return vertex;
}

function kruskal(vertices: string[], edges: Edge[]): { tree: Edge[]; skipped: Edge[] } {
  const parent = new Map(vertices.map((vertex) => [vertex, vertex]));
  const size = new Map(vertices.map((vertex) => [vertex, 1]));
  const tree: Edge[] = [];
  const skipped: Edge[] = [];
  for (const edge of [...edges].sort((a, b) => a[2] - b[2])) {
    if (tree.length === vertices.length - 1) break;
    let rootU = find(parent, edge[0]);
    let rootV = find(parent, edge[1]);
    if (rootU === rootV) {
      skipped.push(edge);
      continue;
    }
    if (size.get(rootU)! < size.get(rootV)!) [rootU, rootV] = [rootV, rootU];
    parent.set(rootV, rootU);
    size.set(rootU, size.get(rootU)! + size.get(rootV)!);
    tree.push(edge);
  }
  return { tree, skipped };
}

const label = (edges: Edge[]): string => edges.map(([u, v, weight]) => `${u}-${v} ${weight}`).join(", ");

const vertices = ["A", "B", "C", "D", "E", "F"];
const edges: Edge[] = [
  ["A", "B", 4], ["A", "C", 1], ["B", "C", 2], ["B", "D", 5], ["C", "D", 8],
  ["C", "E", 9], ["D", "E", 3], ["D", "F", 7], ["E", "F", 6],
];
const { tree, skipped } = kruskal(vertices, edges);
console.log(`tree: ${label(tree)}`);
console.log(`skipped: ${label(skipped)}`);
console.log(`total: ${tree.reduce((sum, [, , weight]) => sum + weight, 0)}`);