Kruskal's Algorithm (Kruskal Algoritması)

1interface Edge {
2  from: string;
3  to: string;
4  weight: number;
5}
6
7interface UnionFind {
8  parent: Map;
9  rank: Map;
10}
11
12function kruskal(nodes: string[], edges: Edge[]) {
13  const sortedEdges = [...edges].sort((a, b) => a.weight - b.weight);
14  const mstEdges: Edge[] = [];
15  const parent = new Map();
16  const rank = new Map();
17
18  nodes.forEach(node => {
19    parent.set(node, node);
20    rank.set(node, 0);
21  });
22
23  function find(node: string): string {
24    if (parent.get(node) !== node) {
25      parent.set(node, find(parent.get(node)!));
26    }
27    return parent.get(node)!;
28  }
29
30  function union(node1: string, node2: string) {
31    const root1 = find(node1);
32    const root2 = find(node2);
33    if (root1 === root2) return;
34    const rank1 = rank.get(root1)!;
35    const rank2 = rank.get(root2)!;
36    if (rank1 < rank2) parent.set(root1, root2);
37    else if (rank1 > rank2) parent.set(root2, root1);
38    else {
39      parent.set(root2, root1);
40      rank.set(root1, rank1 + 1);
41    }
42  }
43
44  let totalWeight = 0;
45  for (const edge of sortedEdges) {
46    if (find(edge.from) !== find(edge.to)) {
47      union(edge.from, edge.to);
48      mstEdges.push(edge);
49      totalWeight += edge.weight;
50      if (mstEdges.length === nodes.length - 1) break;
51    }
52  }
53  return { mstEdges, totalWeight };
54}