อัลกอริทึมของคร้สคัล เป็นอัลกอริทึมในทฤษฎีบทเกียวกับกราฟ โดยจะทำการหา minimum spanning tree จากน้ำหนักของเส้นเชื่อมต่อกราฟ แปลความหมายง่ายๆ ก็คือ การหาเส้นเชือมระหว่างจุดที่มีค่าระยะทางที่น้อยที่สุด และไม่ทำให้เกิดลูปขึ้นในกราฟ . อัลกอริทึมของคร้สคัลเป็นหนึ่งใน greedy algorithm
คำอธิบาย[]
เมื่อ E คือจำนวนเส้นในกราฟ V คือจำนวนจุดในกราฟ อัลกอริทึมของคร้สคัล จะใช้เวลาในการทำงานเป็น O(E log E) หรือเท่ากับ O(E log V) เพราะว่า
E เป็นค่าที่มากที่สุดของ V2 และ logV2 = 2logV ก็คือ O(log V).
ถ้าเราไม่สนใจจุดสิ้นสุดของ minimum spanning tree เวลาที่ได้จะเป็น V ≤ E+1, ดังนั้น log V ก็คือ O(log E).
Kruskal ‘s algorithm[]
Procedure Kruskal ( G : weighted connected undirected graph with n vertices) T := empty graph
for i := 1 to n – 1
begin
e:= any edge in G with smallest weight that does not from a simple circuit when added to T
T := T with e added
end {T is a minimum spanning tree of G}
ตัวอย่าง[]
| รูป | คำบรรยาย |
|---|---|
|
เริ่มแรกของ อัลกอริทึ่มของครัสคัล จะเลือกเส้นที่มีค่าระยะทางต่ำที่สุดก่อน นั้นคือเส้น KG ตามตัวอย่าง |
|
ต่อมาก็ทำการเลือกเส้นที่มีขนาดน้อยที่สุดเป็นลำดับต่อมา ตามตัวอย่างจะมีเส้น IC กับ GF ที่มีระยะทาง 2 เหมือนกันซึ่งในตัวอย่างได้เลือก IC ก่อน |
|
เลือกเส้นที่น้อยที่สุดเป็นลำดับต่อมาคือเส้น GF |
|
หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น AB กับ CF ที่มีระยะทาง 4 เหมือนกันและในตัวอย่างได้เลือก AB ก่อน |
|
เลือกเส้นที่น้อยที่สุดเป็นลำดับต่อมาคือเส้น CF |
|
เส้นที่มีขนาดน้อยที่สุดเป็นลำดับต่อมาคือเส้น IG ที่มีระยะทาง 6 แต่ถ้าเลือกเส้นนี้แล้วจะเกิดการวนลูป IGFC จึงต้องปล่อยไป |
|
หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น CD กับ KI ที่มีระยะทาง 7 เหมือนกันและในตัวอย่างได้เลือก CD ก่อน |
|
เส้นที่มีขนาดน้อยที่สุดเป็นลำดับต่อมาคือเส้น KI แต่ถ้าเลือกเส้นนี้แล้วจะเกิดการวนลูป KGFCI จึงต้องปล่อยไป |
|
หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น AH กับ BC ที่มีระยะทาง 8 เหมือนกันและในตัวอย่างได้เลือก AH ก่อน |
|
เส้นที่มีขนาดน้อยที่สุดเป็นลำดับต่อมาคือเส้น BC แต่ถ้าเลือกเส้นนี้แล้วจะเกิดการวนลูป BAHGFC จึงต้องปล่อยไป |
|
หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น DE ที่มีระยะทาง 9 และไม่ทำให้เกิดการวนลูปจึงเลือกเส้นนี้ |
|
หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น EF ที่มีระยะทาง 10 แต่ทำให้เกิดการวนลูป EDCF จึงต้องปล่อยไป |
|
หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น BH ที่มีระยะทาง 11 แต่ทำให้เกิดการวนลูป ABH จึงต้องปล่อยไป |
|
เส้นสุดท้ายที่มีระยะทางมากที่สุด คือเส้น DF ในระยะทาง 14 แต่ก็ทำให้เกิดลูป DCF จึงต้องปล่อยไป
แล้วก็จะสำเร็จเป็น minimum spanning tree ตามอัลกอริทึมของครัสคัล |
คำที่เกี่ยวข้อง[]
minimum spanning tree กราฟรูปต้นไม้ที่มีค่า cost ในการเดินทางไปยังจุดต่างๆน้อยที่สุด ใช้สำหรับการต่อวงจรต่างๆ
อัลกอริทึมของพริม อีกรูปแบบนึงของการหา minimum spanning tree
เอกสารอ้างอิง[]
- Joseph. B. Kruskal: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.
- Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java, Fourth Edition. John Wiley & Sons, Inc., 2006. ISBN 0-471-73884-0. Section 13.7.1: Kruskal's Algorithm, pp.632.
แหล่งข้อมูลภายนอก[]
http://en.wikipedia.org/wiki/Kruskal%27s_algorithm
std.kku.ac.th/4930401497/SlideData/Ch9x.ppt
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml