FANDOM


อัลกอริทึมของคร้สคัล เป็นอัลกอริทึมในทฤษฎีบทเกียวกับกราฟ โดยจะทำการหา minimum spanning tree จากน้ำหนักของเส้นเชื่อมต่อกราฟ แปลความหมายง่ายๆ ก็คือ การหาเส้นเชือมระหว่างจุดที่มีค่าระยะทางที่น้อยที่สุด และไม่ทำให้เกิดลูปขึ้นในกราฟ . อัลกอริทึมของคร้สคัลเป็นหนึ่งใน greedy algorithm

คำอธิบายEdit

เมื่อ 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 algorithmEdit

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}


ตัวอย่างEdit

รูป คำบรรยาย
Kruskal1 เริ่มแรกของ อัลกอริทึ่มของครัสคัล จะเลือกเส้นที่มีค่าระยะทางต่ำที่สุดก่อน นั้นคือเส้น KG ตามตัวอย่าง
Kruskal2 ต่อมาก็ทำการเลือกเส้นที่มีขนาดน้อยที่สุดเป็นลำดับต่อมา ตามตัวอย่างจะมีเส้น IC กับ GF ที่มีระยะทาง 2 เหมือนกันซึ่งในตัวอย่างได้เลือก IC ก่อน
Kruskal3 เลือกเส้นที่น้อยที่สุดเป็นลำดับต่อมาคือเส้น GF
Kruskal4 หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น AB กับ CF ที่มีระยะทาง 4 เหมือนกันและในตัวอย่างได้เลือก AB ก่อน
Kruskal5 เลือกเส้นที่น้อยที่สุดเป็นลำดับต่อมาคือเส้น CF
Kruskal6 เส้นที่มีขนาดน้อยที่สุดเป็นลำดับต่อมาคือเส้น IG ที่มีระยะทาง 6 แต่ถ้าเลือกเส้นนี้แล้วจะเกิดการวนลูป IGFC จึงต้องปล่อยไป
Kruskal7 หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น CD กับ KI ที่มีระยะทาง 7 เหมือนกันและในตัวอย่างได้เลือก CD ก่อน
Kruskal8 เส้นที่มีขนาดน้อยที่สุดเป็นลำดับต่อมาคือเส้น KI แต่ถ้าเลือกเส้นนี้แล้วจะเกิดการวนลูป KGFCI จึงต้องปล่อยไป
Kruskal9 หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น AH กับ BC ที่มีระยะทาง 8 เหมือนกันและในตัวอย่างได้เลือก AH ก่อน
Kruskal10 เส้นที่มีขนาดน้อยที่สุดเป็นลำดับต่อมาคือเส้น BC แต่ถ้าเลือกเส้นนี้แล้วจะเกิดการวนลูป BAHGFC จึงต้องปล่อยไป
Kruskal11 หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น DE ที่มีระยะทาง 9 และไม่ทำให้เกิดการวนลูปจึงเลือกเส้นนี้
Kruskal12 หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น EF ที่มีระยะทาง 10 แต่ทำให้เกิดการวนลูป EDCF จึงต้องปล่อยไป
Kruskal13 หาเส้นที่มีขนาดน้อยที่สุดเป้นลำดับต่อมา ซึ่งก็คือเส้น BH ที่มีระยะทาง 11 แต่ทำให้เกิดการวนลูป ABH จึงต้องปล่อยไป
Kruskal14 เส้นสุดท้ายที่มีระยะทางมากที่สุด คือเส้น DF ในระยะทาง 14 แต่ก็ทำให้เกิดลูป DCF จึงต้องปล่อยไป

แล้วก็จะสำเร็จเป็น minimum spanning tree ตามอัลกอริทึมของครัสคัล


คำที่เกี่ยวข้องEdit

minimum spanning tree กราฟรูปต้นไม้ที่มีค่า cost ในการเดินทางไปยังจุดต่างๆน้อยที่สุด ใช้สำหรับการต่อวงจรต่างๆ

อัลกอริทึมของพริม อีกรูปแบบนึงของการหา minimum spanning tree


เอกสารอ้างอิงEdit

แหล่งข้อมูลภายนอกEdit

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