En Kısa Yollar ve MST (Shortest Paths & MST) Algoritması

1function getEuclideanDistance(p1: [number, number], p2: [number, number]): number {
2  return Math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2);
3}
4
5function buildEuclideanMST(points: [number, number][]): Array<{ u: number; v: number; weight: number }> {
6  const n = points.length;
7  const edges: Array<{ u: number; v: number; weight: number }> = [];
8
9  // 1. Tüm çiftler arası kenarları hesapla
10  for (let i = 0; i < n; i++) {
11    for (let j = i + 1; j < n; j++) {
12      edges.push({ u: i, v: j, weight: getEuclideanDistance(points[i], points[j]) });
13    }
14  }
15
16  // 2. Kruskal çalıştır
17  edges.sort((a, b) => a.weight - b.weight);
18  const parent = Array.from({ length: n }, (_, i) => i);
19
20  function find(i: number): number {
21    if (parent[i] === i) return i;
22    return (parent[i] = find(parent[i]));
23  }
24
25  const mst: Array<{ u: number; v: number; weight: number }> = [];
26  for (const edge of edges) {
27    const rootU = find(edge.u);
28    const rootV = find(edge.v);
29    if (rootU !== rootV) {
30      mst.push(edge);
31      parent[rootU] = rootV;
32      if (mst.length === n - 1) break;
33    }
34  }
35  return mst;
36}