เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด

Q: Minimum Spanning Tree (MST) คืออะไร?

ต้นไม้แผ่ทั่วน้อยสุด (Minimum Spanning Tree) คือเซตย่อยของขอบจากกราฟแบบไม่มีทิศทางและมีน้ำหนักที่เชื่อมต่อกัน ซึ่งเชื่อมทุกจุดยอดเข้าด้วยกันโดยมีน้ำหนักขอบรวมน้อยที่สุดเท่าที่จะเป็นไปได้ โดยไม่ทำให้เกิดวงจร (Cycle) MST จะมีขอบทั้งหมด V-1 ขอบสำหรับกราฟที่มี V จุดยอด

Q: อัลกอริทึมของ Kruskal และ Prim แตกต่างกันอย่างไร?

อัลกอริทึมของ Kruskal เน้นที่ขอบ: โดยจะเรียงลำดับขอบทั้งหมดตามน้ำหนักและเลือกขอบที่ไม่ทำให้เกิดวงจรอย่างต่อเนื่อง โดยใช้โครงสร้างข้อมูล Union-Find ส่วนอัลกอริทึมของ Prim เน้นที่จุดยอด: โดยจะขยาย MST จากโหนดเริ่มต้นโดยการเพิ่มขอบที่ถูกที่สุดที่เชื่อมต่อต้นไม้กับจุดยอดใหม่เสมอ โดยใช้คิวลำดับความสำคัญ ทั้งสองวิธีให้ MST ที่เหมาะสมที่สุด แต่อาจมีลำดับการเลือกขอบที่ต่างกัน

Q: ควรใช้ Kruskal หรือ Prim เมื่อใด?

Kruskal มักจะดีกว่าสำหรับกราฟที่เบาบาง (มีขอบน้อยเมื่อเทียบกับโหนด) โดยมีความซับซ้อนของเวลา O(E log E) Prim จะดีกว่าสำหรับกราฟที่หนาแน่น โดยมีความซับซ้อนของเวลา O(E log V) เมื่อใช้ Binary Heap สำหรับกราฟที่หนาแน่นมาก Prim ที่ใช้ Fibonacci Heap จะทำเวลาได้ O(E + V log V)

Q: กราฟหนึ่งสามารถมี MST ที่ถูกต้องหลายแบบได้หรือไม่?

ได้ กราฟสามารถมี MST ที่ถูกต้องได้หลายชุดหากมีขอบที่มีน้ำหนักเท่ากัน MST ที่ต่างกันจะมีน้ำหนักรวมเท่ากันแต่อาจประกอบด้วยขอบที่ต่างกัน Kruskal และ Prim อาจให้ MST ที่ต่างกันสำหรับกราฟเดียวกัน แต่ทั้งคู่จะมีน้ำหนักรวมน้อยที่สุดเท่ากัน

Q: การประยุกต์ใช้ MST ในโลกแห่งความเป็นจริงมีอะไรบ้าง?

MST ถูกใช้ในการออกแบบเครือข่าย (ลดความยาวสายเคเบิล/ไฟเบอร์), การวางผังแผงวงจร, การวิเคราะห์กลุ่ม (Cluster Analysis), การแบ่งส่วนภาพ (Image Segmentation), การสร้างอนุกรมวิธาน, การประมาณค่าปัญหา NP-hard เช่น Traveling Salesman Problem (TSP) และการสร้างเครือข่ายถนน/ท่อส่ง/ไฟฟ้าด้วยต้นทุนต่ำสุด

Q: MST ทำงานกับกราฟที่ไม่เชื่อมต่อกันได้หรือไม่?

MST ที่แท้จริงต้องใช้กราฟที่เชื่อมต่อกัน หากกราฟไม่เชื่อมต่อกัน อัลกอริทึมจะสร้าง Minimum Spanning Forest ซึ่งเป็นกลุ่มของ MST สำหรับแต่ละส่วนที่เชื่อมต่อกัน เครื่องคำนวณนี้จะระบุเมื่อกราฟเชื่อมต่อกันไม่สมบูรณ์

คำนวณต้นไม้แผ่ทั่วน้อยสุด (MST) ของกราฟถ่วงน้ำหนักโดยใช้อัลกอริทึมของ Kruskal หรือ Prim มาพร้อมการแสดงภาพกราฟแบบโต้ตอบ การติดตามอัลกอริทึมทีละขั้นตอน และแอนิเมชันการเลือกเส้นเชื่อม

เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด

ลองใช้กราฟตัวอย่างเหล่านี้:

แบบง่าย (5 โหนด) แบบเครือข่าย (7 โหนด) Prim (6 โหนด) ขนาดใหญ่ (12 โหนด)

ขอบของกราฟ (Graph Edges)

อัลกอริทึม

โหนดเริ่มต้น (เฉพาะ Prim)

รูปแบบ: node1, node2, weight — บรรทัดละหนึ่งขอบ MST ทำงานบนกราฟแบบไม่มีทิศทาง น้ำหนักต้องไม่เป็นค่าลบ

Embed เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด Widget

เกี่ยวกับ เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด

ยินดีต้อนรับสู่ เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด เครื่องมือโต้ตอบสำหรับคำนวณ MST ของกราฟแบบมีน้ำหนักโดยใช้อัลกอริทึมของ Kruskal หรือ Prim ไม่ว่าคุณจะกำลังศึกษาทฤษฎีกราฟ ออกแบบโครงสร้างพื้นฐานเครือข่าย หรือปรับการจัดสรรทรัพยากรให้เหมาะสม เครื่องคำนวณนี้จะช่วยให้คุณสำรวจสองอัลกอริทึมพื้นฐานในการหาค่าที่เหมาะสมที่สุดเชิงจัดหมู่ (combinatorial optimization) ผ่านภาพจำลองและขั้นตอนที่ชัดเจน

Minimum Spanning Tree (MST) คืออะไร?

ต้นไม้แผ่ทั่วน้อยสุด ของกราฟแบบเชื่อมต่อกัน ไม่มีทิศทาง และมีน้ำหนัก คือเซตย่อยของขอบที่:

เชื่อมต่อจุดยอดทั้งหมดเข้าด้วยกัน (spanning)
ไม่มีวงจร (tree)
มีน้ำหนักขอบรวมน้อยที่สุดเท่าที่เป็นไปได้

สำหรับกราฟที่มีจุดยอด V จุดยอด MST จะมีขอบทั้งหมด V - 1 ขอบเสมอ หากกราฟไม่เชื่อมต่อกัน ผลลัพธ์จะเป็น Minimum Spanning Forest — ซึ่งคือกลุ่มของ MST สำหรับแต่ละส่วนที่เชื่อมต่อกัน (connected component)

คุณสมบัติของ MST

$$|E_{MST}| = |V| - 1 \quad \text{และ} \quad W_{MST} = \sum_{e \in E_{MST}} w(e) \text{ มีค่าน้อยที่สุด}$$

อัลกอริทึมของ Kruskal

อัลกอริทึมของ Kruskal เป็นอัลกอริทึมแบบละโมบ (greedy algorithm) ที่เน้นขอบ โดยสร้าง MST จากการประมวลผลขอบตามลำดับน้ำหนักที่เพิ่มขึ้น ใช้โครงสร้างข้อมูล Union-Find (Disjoint Set Union) เพื่อตรวจจับวงจรอย่างมีประสิทธิภาพ

รหัสเทียมของ Kruskal

function Kruskal(Graph):
  MST ← เซตว่าง
  เรียงลำดับขอบทั้งหมดตามน้ำหนัก (น้อยไปมาก)
  สร้าง Union-Find สำหรับจุดยอดทั้งหมด

  for each ขอบ (u, v, w) ในขอบที่เรียงลำดับแล้ว:
    if Find(u) ≠ Find(v): // อยู่คนละส่วนประกอบกัน
      MST ← MST ∪ {(u, v, w)}
      Union(u, v) // รวมส่วนประกอบเข้าด้วยกัน

  return MST

ความซับซ้อนของเวลาของ Kruskal

$$O(E \log E) = O(E \log V)$$

อัลกอริทึมของ Prim

อัลกอริทึมของ Prim เป็นอัลกอริทึมแบบละโมบที่เน้นจุดยอด โดยขยาย MST จากจุดยอดเริ่มต้น ในแต่ละขั้นตอนจะเพิ่มขอบที่ถูกที่สุดที่เชื่อมจุดยอดในต้นไม้กับจุดยอดที่อยู่นอกต้นไม้

รหัสเทียมของ Prim

function Prim(Graph, start):
  MST ← เซตว่าง
  inMST ← {start}
  PQ ← คิวลำดับความสำคัญพร้อมขอบจากโหนดเริ่มต้น

  while PQ ไม่ว่าง and |inMST| < |V|:
    (w, u, v) ← ดึงค่าที่น้อยที่สุดจาก PQ
    if v ∉ inMST:
      MST ← MST ∪ {(u, v, w)}
      inMST ← inMST ∪ {v}
      เพิ่มขอบทั้งหมดจาก v ลงใน PQ

  return MST

ความซับซ้อนของเวลาของ Prim (Binary Heap)

$$O((V + E) \log V)$$

Kruskal เทียบกับ Prim: ควรเลือกใช้ตัวไหน?

คุณสมบัติ	Kruskal	Prim
แนวทาง	เน้นขอบ (เรียงลำดับทั่วโลก)	เน้นจุดยอด (ขยายในพื้นที่)
โครงสร้างข้อมูล	Union-Find	Priority Queue
ความซับซ้อนของเวลา	$ O(E \log E) $	$ O((V + E) \log V) $
เหมาะสำหรับ	กราฟเบาบาง (Sparse)	กราฟหนาแน่น (Dense)
กราฟที่ไม่เชื่อมต่อกัน	สร้าง Spanning Forest	แผ่ขยายเฉพาะส่วนของโหนดเริ่มต้น
การทำงานแบบขนาน	ทำได้ง่ายกว่า	มีลักษณะแบบลำดับ

วิธีใช้งานเครื่องคำนวณนี้

กำหนดขอบกราฟ: ป้อนขอบในรูปแบบ node1, node2, weight บรรทัดละหนึ่งขอบ MST ทำงานบนกราฟแบบไม่มีทิศทาง ดังนั้นขอบแต่ละเส้นจะเชื่อมต่อทั้งสองทิศทาง
เลือกอัลกอริทึม: เลือก Kruskal สำหรับกราฟเบาบาง หรือ Prim สำหรับกราฟหนาแน่น ทั้งสองวิธีจะได้ MST ที่เหมาะสมที่สุด
ตั้งค่าโหนดเริ่มต้น (เฉพาะ Prim): กำหนดจุดที่อัลกอริทึมของ Prim จะเริ่มต้น (ไม่บังคับ) ซึ่งจะมีผลต่อลำดับการเลือกขอบแต่ไม่มีผลต่อน้ำหนักรวมของ MST
คำนวณ MST: คลิก "ค้นหา MST" เพื่อรันอัลกอริทึม สำรวจการแสดงภาพแบบโต้ตอบ ตารางขอบ และการติดตามทีละขั้นตอน
ไล่ดูขั้นตอน: ใช้ปุ่ม "ถัดไป/ก่อนหน้า" เพื่อดูการทำงานของอัลกอริทึมทีละขั้น พร้อมการไฮไลต์บนแคนวาสแบบเรียลไทม์

ทำความเข้าใจผลลัพธ์

ตารางขอบ MST

แสดงขอบแต่ละเส้นที่ถูกเลือกสำหรับ MST ตามลำดับที่ถูกเพิ่ม พร้อมน้ำหนักของแต่ละขอบและน้ำหนักรวมของ MST

การแสดงภาพกราฟ

แคนวาสแบบโต้ตอบจะแสดงกราฟของคุณพร้อมองค์ประกอบที่ใช้สีแยกประเภท:

โหนดและขอบสีเขียว = ส่วนหนึ่งของ MST
ไฮไลต์สีส้ม = กำลังถูกพิจารณาอยู่ในขณะนั้น
องค์ประกอบสีเทา = ยังไม่ได้เป็นส่วนหนึ่งของ MST

การติดตามทีละขั้นตอน

แสดงการตัดสินใจของแต่ละอัลกอริทึม: ขอบใดที่กำลังตรวจสอบ ถูกยอมรับหรือปฏิเสธ (และเพราะเหตุใด) และสถานะปัจจุบันของการสร้าง MST

การประยุกต์ใช้ MST ในโลกแห่งความเป็นจริง

การออกแบบเครือข่าย

แอปพลิเคชันที่คลาสสิกที่สุด เมื่อต้องการเชื่อมต่อโหนด (เมือง, เซิร์ฟเวอร์, อุปกรณ์ไฟฟ้า) ด้วยความยาวสายเคเบิล ไฟเบอร์ หรือท่อส่งรวมที่น้อยที่สุด MST จะให้ทางออกที่เหมาะสมที่สุด บริษัทโทรคมนาคมใช้อัลกอริทึมที่อิงตาม MST เพื่อลดต้นทุนโครงสร้างพื้นฐาน

การวิเคราะห์กลุ่ม (Cluster Analysis)

ในด้านการเรียนรู้ของเครื่องและวิทยาศาสตร์ข้อมูล การจัดกลุ่มตาม MST (เช่น Single-linkage clustering) จะจัดกลุ่มข้อมูลโดยการลบขอบที่ยาวที่สุดออกจาก MST วิธีนี้จะสร้างกลุ่มตามธรรมชาติโดยไม่ต้องกำหนดจำนวนกลุ่มล่วงหน้า

การแบ่งส่วนภาพ (Image Segmentation)

อัลกอริทึมคอมพิวเตอร์วิทัศน์ใช้ MST เพื่อแบ่งภาพออกเป็นส่วนที่มีความหมาย โดยพิกเซลคือโหนด น้ำหนักขอบแทนความแตกต่างของสี/ความเข้ม และการตัดขอบ MST จะช่วยแยกวัตถุที่ต่างกันออกจากกัน

อัลกอริทึมการประมาณค่า

MST ให้ค่าประมาณแบบ 2-approximation สำหรับปัญหา Traveling Salesman Problem (TSP) ในเชิงเมตริก น้ำหนักของ MST คือขอบเขตล่างของเส้นทาง TSP ที่เหมาะสมที่สุด และการเพิ่มขอบ MST เป็นสองเท่าจะได้เส้นทางที่ไม่เกิน 2 เท่าของค่าที่เหมาะสมที่สุด

การออกแบบวงจร

การออกแบบชิป VLSI ใช้ MST (ผ่าน Steiner tree variants) เพื่อลดความยาวสายไฟรวมที่เชื่อมต่อส่วนประกอบบนแผงวงจร ช่วยลดความล่าช้าของสัญญาณและต้นทุนการผลิต

คุณสมบัติหลักของ MST

Cut Property: สำหรับการตัด (Cut) ใดๆ ในกราฟ ขอบที่มีน้ำหนักน้อยที่สุดที่ข้ามผ่านรอยตัดนั้นจะอยู่ใน MST
Cycle Property: สำหรับวงจร (Cycle) ใดๆ ในกราฟ ขอบที่มีน้ำหนักมากที่สุดในวงจรนั้นจะไม่อยู่ใน MST (ในกรณีที่น้ำหนักไม่ซ้ำกัน)
ความเฉพาะตัว: หากน้ำหนักของขอบทั้งหมดแตกต่างกัน MST จะมีเพียงชุดเดียว หากมีน้ำหนักซ้ำกัน อาจมี MST ที่ถูกต้องได้หลายชุดแต่จะมีน้ำหนักรวมเท่ากันเสมอ
กราฟย่อย: MST คือกราฟย่อยที่มี V-1 ขอบและไม่มีวงจร

คำถามที่พบบ่อย

Minimum Spanning Tree (MST) คืออะไร?

ต้นไม้แผ่ทั่วน้อยสุด คือเซตย่อยของขอบจากกราฟแบบไม่มีทิศทางและมีน้ำหนักที่เชื่อมต่อกัน ซึ่งเชื่อมทุกจุดยอดเข้าด้วยกันโดยมีน้ำหนักขอบรวมน้อยที่สุดเท่าที่จะเป็นไปได้ โดยไม่ทำให้เกิดวงจร MST จะมีขอบทั้งหมด V-1 ขอบสำหรับกราฟที่มี V จุดยอด

อัลกอริทึมของ Kruskal และ Prim แตกต่างกันอย่างไร?

อัลกอริทึมของ Kruskal เน้นที่ขอบ: โดยจะเรียงลำดับขอบทั้งหมดตามน้ำหนักและเลือกขอบที่ไม่ทำให้เกิดวงจรอย่างต่อเนื่อง โดยใช้โครงสร้างข้อมูล Union-Find ส่วนอัลกอริทึมของ Prim เน้นที่จุดยอด: โดยจะขยาย MST จากโหนดเริ่มต้นโดยการเพิ่มขอบที่ถูกที่สุดที่เชื่อมต่อต้นไม้กับจุดยอดใหม่เสมอ โดยใช้คิวลำดับความสำคัญ ทั้งสองวิธีให้ MST ที่เหมาะสมที่สุด แต่อาจมีลำดับการเลือกขอบที่ต่างกัน

ควรใช้ Kruskal หรือ Prim เมื่อใด?

Kruskal มักจะดีกว่าสำหรับกราฟที่เบาบาง (มีขอบน้อยเมื่อเทียบกับโหนด) โดยมีความซับซ้อนของเวลา O(E log E) Prim จะดีกว่าสำหรับกราฟที่หนาแน่น โดยมีความซับซ้อนของเวลา O(E log V) เมื่อใช้ Binary Heap สำหรับกราฟที่หนาแน่นมาก Prim ที่ใช้ Fibonacci Heap จะทำเวลาได้ O(E + V log V)

กราฟหนึ่งสามารถมี MST ที่ถูกต้องหลายแบบได้หรือไม่?

ได้ กราฟสามารถมี MST ที่ถูกต้องได้หลายชุดหากมีขอบที่มีน้ำหนักเท่ากัน MST ที่ต่างกันจะมีน้ำหนักรวมเท่ากันแต่อาจประกอบด้วยขอบที่ต่างกัน Kruskal และ Prim อาจให้ MST ที่ต่างกันสำหรับกราฟเดียวกัน แต่ทั้งคู่จะมีน้ำหนักรวมน้อยที่สุดเท่ากัน

การประยุกต์ใช้ MST ในโลกแห่งความเป็นจริงมีอะไรบ้าง?

MST ถูกใช้ในการออกแบบเครือข่าย (ลดความยาวสายเคเบิล/ไฟเบอร์), การวางผังแผงวงจร, การวิเคราะห์กลุ่ม (Cluster Analysis), การแบ่งส่วนภาพ (Image Segmentation), การสร้างอนุกรมวิธาน, การประมาณค่าปัญหา NP-hard เช่น Traveling Salesman Problem (TSP) และการสร้างเครือข่ายถนน/ท่อส่ง/ไฟฟ้าด้วยต้นทุนต่ำสุด

MST ทำงานกับกราฟที่ไม่เชื่อมต่อกันได้หรือไม่?

MST ที่แท้จริงต้องใช้กราฟที่เชื่อมต่อกัน หากกราฟไม่เชื่อมต่อกัน อัลกอริทึมจะสร้าง Minimum Spanning Forest — ซึ่งเป็นกลุ่มของ MST สำหรับแต่ละส่วนที่เชื่อมต่อกัน เครื่องคำนวณนี้จะระบุเมื่อกราฟเชื่อมต่อกันไม่สมบูรณ์

แหล่งข้อมูลเพิ่มเติม

อ้างอิงเนื้อหา หน้าหรือเครื่องมือนี้ว่า:

"เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด" ที่ https://MiniWebtool.com/th// จาก MiniWebtool, https://MiniWebtool.com/

โดย ทีมงาน miniwebtool อัปเดตเมื่อ: 19 ก.พ. 2026

คุณสามารถลองใช้ AI แก้ปัญหาคณิตศาสตร์ GPT ของเรา เพื่อแก้ไขปัญหาทางคณิตศาสตร์ของคุณผ่านคำถามและคำตอบด้วยภาษาธรรมชาติ.

เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด

ตัวบล็อกโฆษณาของคุณทำให้เราไม่สามารถแสดงโฆษณาได้

เกี่ยวกับ เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด

Minimum Spanning Tree (MST) คืออะไร?

อัลกอริทึมของ Kruskal

รหัสเทียมของ Kruskal

อัลกอริทึมของ Prim

รหัสเทียมของ Prim

Kruskal เทียบกับ Prim: ควรเลือกใช้ตัวไหน?

วิธีใช้งานเครื่องคำนวณนี้

ทำความเข้าใจผลลัพธ์

ตารางขอบ MST

การแสดงภาพกราฟ

การติดตามทีละขั้นตอน

การประยุกต์ใช้ MST ในโลกแห่งความเป็นจริง

การออกแบบเครือข่าย

การวิเคราะห์กลุ่ม (Cluster Analysis)

การแบ่งส่วนภาพ (Image Segmentation)

อัลกอริทึมการประมาณค่า

การออกแบบวงจร

คุณสมบัติหลักของ MST

คำถามที่พบบ่อย

Minimum Spanning Tree (MST) คืออะไร?

อัลกอริทึมของ Kruskal และ Prim แตกต่างกันอย่างไร?

ควรใช้ Kruskal หรือ Prim เมื่อใด?

กราฟหนึ่งสามารถมี MST ที่ถูกต้องหลายแบบได้หรือไม่?

การประยุกต์ใช้ MST ในโลกแห่งความเป็นจริงมีอะไรบ้าง?

MST ทำงานกับกราฟที่ไม่เชื่อมต่อกันได้หรือไม่?

แหล่งข้อมูลเพิ่มเติม

เครื่องมือเด่น: