ตั้งแต่ปี 2010 · รองรับการใช้งานเครื่องมือกว่า 2 ล้านครั้งต่อเดือน
ตั้งแต่ปี 2010
เพิ่มใน Chrome

กล่องเครื่องมือของฉัน

โหมดอัตโนมัติ

ยังไม่มีเครื่องมือที่บันทึกไว้

อัปเกรดเป็นเวอร์ชันพรีเมียม
เครื่องมือที่เกี่ยวข้อง
เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตราเครื่องคำนวณการระบายสีกราฟเครื่องตรวจสอบลำดับดีกรีของกราฟเครื่องคำนวณการเรียงลำดับทอพอโลยี
หน้าแรก > คณิตศาสตร์ > การดำเนินการทางคณิตศาสตร์ขั้นสูง
 

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

ใส่กราฟถ่วงน้ำหนักได้ถึง 50 จุดยอดและ 200 เส้นเชื่อม เพื่อหาต้นไม้แผ่ทั่วที่น้อยสุดด้วยขั้นตอนของครัสคัลหรือพริม พร้อมขั้นตอนที่เห็นเป็นภาพ.

ใช้งานฟรีไม่ต้องสมัครสมาชิกอัปเดต ก.พ. 2026
เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุดลองใช้เลย — ฟรี ▼

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

แบบง่าย (5 โหนด) แบบเครือข่าย (7 โหนด) Prim (6 โหนด) ขนาดใหญ่ (12 โหนด)
รูปแบบ: 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: ควรเลือกใช้ตัวไหน?

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

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

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

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

ตารางขอบ 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

การดำเนินการทางคณิตศาสตร์ขั้นสูง:

ตัวช่วยแก้โจทย์คณิตศาสตร์คุณต้องการคำนวณอะไร?

ตัวช่วยแก้โจทย์คณิตศาสตร์

ตัวอย่าง
ดูตัวอย่างนิพจน์เพิ่มเติม

เลือกตัวอย่าง แก้ไขตัวเลข แล้วคำนวณ log ใช้ฐาน 10 ส่วน ln คือลอการิทึมธรรมชาติ

จำนวนและตัวประกอบ

เศษส่วนและการหาร

เลขยกกำลัง ราก และลอการิทึม

พีชคณิตและสมการ

แคลคูลัส

เรขาคณิตและตรีโกณมิติ

เครื่องมือยอดนิยมและอัปเดตล่าสุด:

ค้นหาค่าต่ำสุดและสูงสุดเครื่องคำนวณราศีต้นไม้เซลติกเครื่องคำนวณต้นคริสต์มาสดูทั้งหมด →
หน้าแรก > คณิตศาสตร์ > การดำเนินการทางคณิตศาสตร์ขั้นสูง > เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด