Spanning Tree
Spanning Tree คือเซตย่อยของ Undirected Graph ที่มี ทุกโหนด (Vertices) เชื่อมต่อ โดยจำนวนขอบ (Edges) น้อยที่สุด
- ถ้าทุกโหนดในกราฟเชื่อมต่อกัน → มี Spanning Tree อย่างน้อย 1 ต้น
- ในกราฟหนึ่ง อาจมี Spanning Tree มากกว่า 1 ต้น
Minimum Spanning Tree (MST)
MST คือเซตย่อยของขอบใน Connected Weighted Undirected Graph ที่เชื่อมโหนดทั้งหมดด้วย น้ำหนักขอบรวมต่ำสุด (Minimum Total Edge Weight)
หา MST ได้ด้วย Prim's Algorithm หรือ Kruskal's Algorithm (บทนี้เน้น Prim's)
ถ้ามี n โหนด Spanning Tree จะมีขอบ n-1 ขอบ หากขอบมีน้ำหนัก และมี Spanning Tree หลายต้น ต้องหาต้นที่น้ำหนักรวมน้อยสุด
ถ้ามีขอบน้ำหนักซ้ำ กราฟอาจมี Multiple MSTs
ตัวอย่าง Spanning Tree (ไม่ใช่ MST) ต้นทุน = (5+7+3+3+5+8+3+4) = 38
