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
12// Kruskal's algorithm for Minimum Spanning Tree
13function kruskal(graph: Graph): {
14  mstEdges: Edge[];
15  totalWeight: number;
16  steps: { edge: Edge; action: 'add' | 'reject'; reason: string }[];
17} {
18  const sortedEdges = [...graph.edges].sort((a, b) => a.weight - b.weight);
19  const mstEdges: Edge[] = [];
20  const steps: { edge: Edge; action: 'add' | 'reject'; reason: string }[] = [];
21  const unionFind = createUnionFind(Array.from(graph.nodes.keys()));
22  let totalWeight = 0;
23
24  // Process edges in order of increasing weight
25  for (const edge of sortedEdges) {
26    const rootFrom = find(unionFind, edge.from);
27    const rootTo = find(unionFind, edge.to);
28
29    // Check if adding this edge would create a cycle
30    if (rootFrom !== rootTo) {
31      union(unionFind, edge.from, edge.to);
32      mstEdges.push(edge);
33      totalWeight += edge.weight;
34      steps.push({ 
35        edge, 
36        action: 'add', 
37        reason: `Added edge (${edge.from} -> ${edge.to}) with weight ${edge.weight}` 
38      });
39      
40      // Stop when we have n-1 edges for n nodes
41      if (mstEdges.length === graph.nodes.size - 1) {
42        break;
43      }
44    } else {
45      steps.push({ 
46        edge, 
47        action: 'reject', 
48        reason: `Rejected edge (${edge.from} -> ${edge.to}) - would create cycle` 
49      });
50    }
51  }
52
53  return { mstEdges, totalWeight, steps };
54}
55
56// Union-Find data structure implementation
57function createUnionFind(nodes: string[]): UnionFind {
58  const parent = new Map();
59  const rank = new Map();
60
61  // Initialize each node as its own parent with rank 0
62  nodes.forEach(node => {
63    parent.set(node, node);
64    rank.set(node, 0);
65  });
66
67  return { parent, rank };
68}
69
70// Find operation with path compression
71function find(unionFind: UnionFind, node: string): string {
72  if (unionFind.parent.get(node) !== node) {
73    // Path compression optimization
74    unionFind.parent.set(node, find(unionFind, unionFind.parent.get(node)!));
75  }
76  return unionFind.parent.get(node)!;
77}
78
79// Union operation by rank
80function union(unionFind: UnionFind, node1: string, node2: string): void {
81  const root1 = find(unionFind, node1);
82  const root2 = find(unionFind, node2);
83
84  if (root1 === root2) return;
85
86  const rank1 = unionFind.rank.get(root1)!;
87  const rank2 = unionFind.rank.get(root2)!;
88
89  // Union by rank optimization
90  if (rank1 < rank2) {
91    unionFind.parent.set(root1, root2);
92  } else if (rank1 > rank2) {
93    unionFind.parent.set(root2, root1);
94  } else {
95    unionFind.parent.set(root2, root1);
96    unionFind.rank.set(root1, rank1 + 1);
97  }
98}
99
100// Usage example
101const graph = createExampleGraph();
102const result = kruskal(graph);
103console.log('MST edges:', result.mstEdges);
104console.log('Total weight:', result.totalWeight);