เมนูนำทาง
ขั้นตอนวิธีของครูสกาล ประสิทธิภาพถ้า E คือจำนวนเส้นเชื่อมในกราฟ และ V คือจำนวนของจุดยอด ขั้นตอนวิธีนี้สามารถทำงานได้ในเวลา O(E log E) หรือเท่ากับ O(E log V) โดยในทุกโครงสร้าข้อมูล เวลาการทำงานจะเท่าเทียมกันเพราะ:
เราสามารถเพิ่มประสิทธิภาพได้ดังนี้ เริ่มจากเรียงลำดับเส้นเชื่อมตามน้ำหนักใช้เวลา O(E log E) ขั้นตอนนี้อนุญาตให้ ลบเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดจาก S เพื่อที่จะดำเนินการในเวลาคงที่ ขั้นตอนต่อไปเราใช้ ข้อมูลแบบเซตไม่ต่อเนื่อง เพื่อเก็บลู่ของจุดยอดต้องการการปฏิบัติการใน O(E) การดำเนินการ ทุกๆ โครงสร้างข้อมูลแบบเซตไม่ต่อเนื่อง สามารถทำได้ปฏิบัติการได้ใน O(E) การดำเนินการ ในเวลา O(E log V) ดังนั้นจะได้เวลารวม O(E log E) = O(E log V)
ถ้าได้เรียงลำดับเส้นเชื่อมก่อนแล้วหรือสามารถเรียงดำลับในเวลาเชิงเส้น (เช่น การเรียงลำดับแบบนับจำนวน (counting sort)) หรือ การเรียงลำดับแบบสมุฎฐาน (radix sort)) ขั้นตอนวิธีนี้ลดความซับซ้อนของโครงสร้างข้อมูลแบบเซตไม่ต่อเนื่อง เพื่อลดเวลาการทำงานใน O(E α(V)) เมื่อ α เป็นค่าที่มีอัตราการเติบโตน้อยมากๆ
เมนูนำทาง
ขั้นตอนวิธีของครูสกาล ประสิทธิภาพใกล้เคียง
ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด 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