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

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

ขั้นตอนวิธีของครูสกาล (อังกฤษ: Kruskal's algorithm) เป็นขั้นตอนวิธีแบบละโมบในทฤษฎีกราฟ ที่ใช้หา ต้นไม้แบบทอดข้ามน้อยสุด (Minimum spanning tree) สำหรับกราฟเชื่อมโยงแบบมีน้ำหนัก นั้นหมายความว่าเราจะได้เซตย่อยของเส้นเชื่อมในต้นไม้ที่เชื่อมทุกๆปม โดยที่ผลรวมของน้ำหนักบนเส้นเชื่อมจะมีค่าน้อยที่สุด หากกราฟไม่เป็นกราฟเชื่อมโยง เราจะได้ ป่าแบบทอดข้ามน้อยสุด (คือต้นไม้แบบทอดข้ามน้อยสุดแต่ละต้นในกราฟ)ขั้นตอนวิธีนี้ปรากฏครั้งแรกบนนิตยสารทางวิทยาศาสตร์ชื่อ Proceedings of the American Mathematical Society หน้า. 48-50 ในปี 1956, และเขียนโดย โจเซฟ ครูสกาลและยังมีขั้นตอนวิธีสำหรับแก้ปัญหาแบบเดียวกัน เช่น ขั้นตอนวิธีของพริม ขั้นตอนวิธีการลบย้อนกลับ และ ขั้นตอนวิธีของโบรุฟกา

ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด 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