ต้นไม้ขยายขั้นต่ำ (MST) ใน JavaScript

ต้นไม้ขยายขั้นต่ำ (Minimum Spanning Tree - MST) คืออะไร

ต้นไม้ขยายขั้นต่ำ (MST) หรือต้นไม้ขยายน้ำหนักขั้นต่ำ คือ ชุดย่อยของเส้นขอบ (edges) ของกราฟที่เชื่อมต่อกัน และมีน้ำหนัก (weighted) ไม่ว่าจะเป็นกราฟมีทิศทาง (directed) หรือไม่มีทิศทาง (undirected) ที่เชื่อมโหนด (vertices) ทั้งหมดเข้าด้วยกัน โดยไม่มีวัฏจักร (cycles) และมีน้ำหนักรวมของเส้นขอบน้อยที่สุด กล่าวคือ เป็นต้นไม้ขยายที่ผลรวมน้ำหนักของเส้นขอบมีค่าน้อยที่สุด

อัลกอริธึมหลักสำหรับหา MST

1. อัลกอริธึมของ Kruskal (Kruskal's Algorithm)

ทำงานโดยการจัดเรียงเส้นขอบทั้งหมดตามน้ำหนักจากน้อยไปมาก แล้วเพิ่มเส้นขอบทีละเส้น โดยข้ามเส้นขอบที่จะสร้างวัฏจักร ใช้โครงสร้างข้อมูล Disjoint Set Union (DSU) เพื่อตรวจสอบวัฏจักร

2. อัลกอริธึมของ Prim (Prim's Algorithm)

เริ่มจากโหนดใดโหนดหนึ่ง แล้วขยายต้นไม้โดยเพิ่มเส้นขอบที่มีน้ำหนักน้อยที่สุดที่เชื่อมระหว่างโหนดในต้นไม้กับโหนดภายนอก ใช้ Priority Queue (Min-Heap) เพื่อเลือกเส้นขอบที่มีน้ำหนักน้อยที่สุด

ตัวอย่างโค้ด JavaScript (Kruskal's Algorithm)

class DSU {
  constructor(n) {
    this.parent = Array.from({length: n}, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}

function kruskalMST(n, edges) {
  edges.sort((a, b) => a.weight - b.weight);
  const dsu = new DSU(n);
  let mstWeight = 0;
  const mstEdges = [];
  for (const {u, v, weight} of edges) {
    if (dsu.union(u, v)) {
      mstWeight += weight;
      mstEdges.push({u, v, weight});
    }
  }
  return {mstWeight, mstEdges};
}

// ตัวอย่างการใช้งาน
const n = 4;
const edges = [
  {u: 0, v: 1, weight: 10},
  {u: 0, v: 2, weight: 6},
  {u: 0, v: 3, weight: 5},
  {u: 1, v: 3, weight: 15},
  {u: 2, v: 3, weight: 4}
];
console.log(kruskalMST(n, edges));
// ผลลัพธ์: { mstWeight: 19, mstEdges: [...] }

การประยุกต์ใช้งาน MST

• การออกแบบเครือข่ายคอมพิวเตอร์ / โทรคมนาคม
• การวางแผนเส้นทางขนส่ง / ท่อส่งน้ำมัน
• การจัดกลุ่มข้อมูล (Clustering)
• การประมาณค่า Traveling Salesman Problem

ความซับซ้อนของเวลา (Time Complexity)