Spanning Tree ขั้นต่ำในโครงสร้างข้อมูล

ต้นไม้ทอดยาว เป็นเซตย่อยของกราฟที่ไม่มีทิศทางซึ่งมีจุดยอดทั้งหมดเชื่อมต่อกันด้วยจำนวนขอบขั้นต่ำ

หากจุดยอดทั้งหมดเชื่อมต่อกันในกราฟ แสดงว่ามีต้นไม้ขยายอย่างน้อยหนึ่งต้น ในกราฟ อาจมีต้นไม้ทอดยาวมากกว่าหนึ่งต้น

ขั้นต่ำ Spanning Tree

ขั้นต่ำ Spanning Tree (MST) เป็นเซตย่อยของขอบของกราฟแบบไม่บอกทิศทางแบบถ่วงน้ำหนักที่เชื่อมต่อกัน ซึ่งเชื่อมต่อจุดยอดทั้งหมดเข้ากับน้ำหนักขอบทั้งหมดต่ำสุดที่เป็นไปได้ เพื่อให้ได้มาซึ่ง MST คุณสามารถใช้อัลกอริธึมของ Prim หรืออัลกอริทึมของ Kruskal ได้ ดังนั้น เราจะพูดถึงอัลกอริทึมของ Prim ในบทนี้

ดังที่เราได้กล่าวไปแล้ว กราฟหนึ่งอาจมีต้นไม้ทอดยาวมากกว่าหนึ่งต้น หากมี n จำนวนจุดยอด ต้นไม้ที่ทอดข้ามควรมี n - 1 จำนวนขอบ ในบริบทนี้ หากขอบแต่ละด้านของกราฟสัมพันธ์กับน้ำหนักและมีต้นไม้ขยายมากกว่าหนึ่งต้น เราต้องหาต้นไม้ที่ทอดข้ามขั้นต่ำของกราฟ

นอกจากนี้ หากมีขอบที่ถ่วงน้ำหนักที่ซ้ำกัน กราฟอาจมีแผนภูมิที่ทอดข้ามขั้นต่ำหลายแบบ

ในกราฟด้านบน เราได้แสดงแผนผังที่ทอดข้าม แม้ว่าจะไม่ใช่แผนภูมิที่ทอดข้ามขั้นต่ำก็ตาม ราคาของต้นไม้ขยายนี้คือ (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) =38.