ต้นไม้ทอดข้ามที่น้อยที่สุด

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

ตัวอย่างการเชื่อมต่อโหนดแต่ละโหนดเข้าหากันด้วยน้ำหนักรวมน้อยที่สุดวิธีหนึ่งจากกราฟถ่วงน้ำหนัก