อธิบาย ของ ขั้นตอนวิธีของครูสกาล

  • สร้างป่า F (เซตของต้นไม้) ที่มีจุดยอดหรือปมในกราฟเป็นต้นไม้
  • สร้างเซต S ที่บรรจุทุกเส้นเชื่อมในกราฟไว้
  • ในขณะที่ S ไม่เป็นเซตว่าง และ F ยังไม่ทอดข้าม
    • ลบเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดจาก S
    • ถ้าเส้นเชื่อมนั้นเชื่อมจุดสองจุดที่ต่างกันบนต้นไม้ แล้วเพิ่มเข้าไปในป่าดังกล่าวรวมต้นไม้สองต้นให้เป็นต้นเดียว

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

ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด k ตัว ขั้นตอนวิธีของฟลอยด์-วอร์แชล ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ ขั้นตอนวิธีฮังกาเรียน ขั้นตอนวิธี ขั้นตอนวิธีของชอร์ ขั้นตอนวิธีเชิงพันธุกรรม ขั้นตอนวิธีโบรน-เคอร์โบสท์ ขั้นตอนวิธีของไดก์สตรา

แหล่งที่มา

WikiPedia: ขั้นตอนวิธีของครูสกาล http://www.carlschroedl.com/blog/comp/kruskals-min... http://www.codeproject.com/KB/recipes/Kruskal_Algo... http://www.programyar.com/wp-content/uploads/2012/... http://scanftree.com/Data_Structure/kruskal's-algo... http://students.ceid.upatras.gr/~papagel/project/k... https://github.com/monmohan/mgraphlib https://docs.google.com/file/d/0B2_b0Jz3VKm8RG8zOT... https://en.wikipedia.org/wiki/Kruskal's_algorithm