อัลกอริทึมของครัสกัล

Q: ข้อมูลสำคัญเกี่ยวกับ อัลกอริทึมของครัสกัล

อัลกอริทึมของ Kruskal ค้นหาป่าครอบคลุมขั้นต่ำของกราฟแบบไม่มีทิศทางที่มีน้ำหนักขอบหากกราฟเชื่อมต่อกัน อัลก

Q: รหัสเทียม

โค้ดต่อไปนี้เขียนขึ้นโดยใช้ โครงสร้างข้อมูลเซตที่ไม่เกี่ยวข้องกัน โดยจะแสดงป่า F เป็นเซตของขอบที่ไม่มีทิศทาง และใช้โครงสร้างข้อมูลเซตที่ไม่เกี่ยวข้องกันเพื่อตรวจสอบอย่างมีประสิทธิภาพว่าจุดยอดสองจุดเป็นส่วนหนึ่งของต้นไม้เดียวกันหรือไม่

อัลกอริทึมของครัสกัล
	ภาพเคลื่อนไหวแสดงการทำงานของอัลกอริทึม Kruskal บนกราฟสมบูรณ์ที่มีค่าน้ำหนักตามระยะทางแบบยุคลิด
ระดับ	อัลกอริทึมต้นไม้ครอบคลุมขั้นต่ำ
โครงสร้างข้อมูล	กราฟ
ประสิทธิภาพในกรณีที่เลวร้ายที่สุด	โอ(\|อี\|บันทึก⁡\|วี\|){\displaystyle O(\|E\|\log \|V\|)}

อัลกอริทึมของ Kruskal ^{[ 1 ]}ค้นหาป่าครอบคลุมขั้นต่ำของกราฟแบบไม่มีทิศทางที่มีน้ำหนักขอบหากกราฟเชื่อมต่อกัน อัลก อริทึมนี้จะค้นหาต้นไม้ครอบคลุมขั้นต่ำเป็นอัลกอริทึมแบบโลภที่ในแต่ละขั้นตอนจะเพิ่มขอบที่มีน้ำหนักต่ำที่สุดที่ไม่ก่อให้เกิดวงจรลงใน ป่า ^{[ 2 ]}ขั้นตอนสำคัญของอัลกอริทึมคือการเรียงลำดับและการใช้โครงสร้างข้อมูลเซตที่ไม่เกี่ยวข้องกันเพื่อตรวจจับวงจร เวลาในการทำงานของอัลกอริทึมนี้ส่วนใหญ่มาจากเวลาในการเรียงลำดับขอบกราฟทั้งหมดตามน้ำหนัก

ต้นไม้แผ่คลุมขั้นต่ำ (Minimum Spanning Tree) ของกราฟถ่วงน้ำหนักที่เชื่อมต่อกัน คือ กราฟย่อยที่เชื่อมต่อกันโดยไม่มีวงจร ซึ่งผลรวมของน้ำหนักของขอบทั้งหมดในกราฟย่อยนั้นมีค่าน้อยที่สุด สำหรับกราฟที่ไม่เชื่อมต่อกัน ป่าแผ่คลุมขั้นต่ำ (Minimum Spanning Forest) ประกอบด้วยต้นไม้แผ่คลุมขั้นต่ำสำหรับแต่ละส่วนประกอบที่เชื่อมต่อกัน

อัลกอริทึมนี้ได้รับการตีพิมพ์ครั้งแรกโดยJoseph Kruskalในปี พ.ศ. 2499 ^{[ 3 ]}และถูกค้นพบอีกครั้งในเวลาต่อมาโดยLoberman & Weinberger (1957) [ ^{4 ] อั}ลกอริทึมอื่นๆ สำหรับปัญหานี้ ได้แก่ อัลกอริทึม ของPrim อัลกอริทึมของ Borůvkaและ อัลกอริ ทึมการลบแบบย้อนกลับ

อัลกอริทึม

อัลกอริทึมจะดำเนินการตามขั้นตอนต่อไปนี้:

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

เมื่ออัลกอริทึมสิ้นสุดลง ป่าดังกล่าวจะกลายเป็นป่าที่แผ่คลุมน้อยที่สุดของกราฟ หากกราฟเชื่อมต่อกัน ป่าจะมีส่วนประกอบเพียงส่วนเดียวและกลายเป็นต้นไม้ที่แผ่คลุมน้อยที่สุด

รหัสเทียม

โค้ดต่อไปนี้เขียนขึ้นโดยใช้โครงสร้างข้อมูลเซตที่ไม่เกี่ยวข้องกันโดยจะแสดงป่าFเป็นเซตของขอบที่ไม่มีทิศทาง และใช้โครงสร้างข้อมูลเซตที่ไม่เกี่ยวข้องกันเพื่อตรวจสอบอย่างมีประสิทธิภาพว่าจุดยอดสองจุดเป็นส่วนหนึ่งของต้นไม้เดียวกันหรือไม่

ฟังก์ชัน Kruskal( กราฟ G ) คือ F:= ∅ สำหรับแต่ละ v ใน G.Vertices ให้ทำดังนี้ สร้าง-ตั้งค่า(v) สำหรับแต่ละ {u, v} ใน G.Edges ที่เรียงลำดับตามน้ำหนักที่เพิ่มขึ้น ({u, v}) ให้ทำดังนี้ถ้า FIND-SET(u) ≠ FIND-SET(v) แล้ว F := F ∪ { {u, v} } UNION(FIND-SET(u), FIND-SET(v)) คืนค่า F

ความซับซ้อน

สำหรับกราฟที่มี ขอบ $E$ และ จุดยอด $V$ อัลกอริทึมของ Kruskal สามารถทำงานได้ในเวลา $O (E log E)$ โดยใช้โครงสร้างข้อมูลที่เรียบง่าย ขอบเขตเวลาดังกล่าวนี้มักเขียนแทนด้วย $O (E log V)$ ซึ่งเทียบเท่ากันสำหรับกราฟที่ไม่มีจุดยอดโดดเดี่ยว เนื่องจากสำหรับกราฟเหล่านี้ $V /2 \leq E < V2$ และค่าลอการิทึมของ $V$ $และ$ V2 $จะ$ $อยู่$ ในช่วงค่าคงที่ของกันและกัน

เพื่อให้บรรลุขอบเขตนี้ ขั้นแรกให้เรียงลำดับขอบตามน้ำหนักโดยใช้การเรียงลำดับแบบเปรียบเทียบใน เวลา $O (E log E)$ เมื่อเรียงลำดับแล้ว จะสามารถวนลูปผ่านขอบตามลำดับที่เรียงแล้วได้ในเวลาคงที่ต่อขอบ จากนั้น ใช้โครงสร้างข้อมูลเซตที่ไม่ทับซ้อนกันโดยมีเซตของจุดยอดสำหรับแต่ละส่วนประกอบ เพื่อติดตามว่าจุดยอดใดอยู่ในส่วนประกอบใด การสร้างโครงสร้างนี้ โดยมีเซตแยกต่างหากสำหรับแต่ละจุดยอด ต้องใช้ การดำเนินการ $V$ และ เวลา $O (V)$ การวนซ้ำครั้งสุดท้ายผ่านขอบทั้งหมดจะดำเนินการค้นหา 2 ครั้ง และอาจมีการดำเนินการรวม 1 ครั้งต่อขอบ การดำเนินการเหล่านี้ใช้เวลาเฉลี่ย $O (α (V))$ ต่อการดำเนินการ ทำให้เวลารวมในกรณีที่เลวร้ายที่สุดคือ $O (E α (V))$ สำหรับลูปนี้ โดยที่ $α คือ$ ฟังก์ชัน Ackermann ผกผันที่เติบโตช้ามากส่วนนี้ของขอบเขตเวลามีขนาดเล็กกว่าเวลาสำหรับขั้นตอนการเรียงลำดับมาก ดังนั้นเวลารวมสำหรับอัลกอริทึมจึงสามารถลดรูปให้เหลือเพียงเวลาสำหรับขั้นตอนการเรียงลำดับได้

ในกรณีที่ขอบได้รับการเรียงลำดับแล้ว หรือมีน้ำหนักจำนวนเต็มที่น้อยพอที่จะทำให้ อัลกอริทึมการ เรียงลำดับจำนวนเต็มเช่นการเรียงลำดับแบบนับหรือการเรียงลำดับแบบฐานสามารถเรียงลำดับได้ในเวลาเชิงเส้น การดำเนินการเซตที่ไม่ทับซ้อนกันจะเป็นส่วนที่เหลือที่ช้าที่สุดของอัลกอริทึม และเวลาทั้งหมดคือO $(E α (V))$

ตัวอย่าง

ภาพ	คำอธิบาย
	ADและCEเป็นขอบที่สั้นที่สุด โดยมีความยาว 5 และ เนื่องจากเลือก ADมาโดยพลการจึงถูกเน้นให้เห็นชัดเจน
	ขณะนี้ CEเป็นขอบที่สั้นที่สุดที่ไม่ก่อให้เกิดวงจร โดยมีความยาว 5 ดังนั้นจึงถูกเน้นให้เป็นขอบที่สอง
	ขอบถัดไปDFที่มีความยาว 6 จะถูกเน้นด้วยวิธีการที่คล้ายคลึงกัน
	ขอบที่สั้นที่สุดถัดไปคือABและBEซึ่งมีความยาว 7 ทั้งคู่เลือกAB โดยพลการและไฮไลต์ไว้ ส่วนขอบ BDถูกไฮไลต์ด้วยสีแดง เนื่องจากมีเส้นทาง (สีเขียว) ระหว่างBและD อยู่แล้ว ดังนั้น หากเลือกขอบBD ก็จะเกิดเป็นวงจร ( ABD )
	กระบวนการนี้ยังคงเน้นขอบที่เล็กที่สุดถัดไป คือBEซึ่งมีความยาว 7 ขอบอีกหลายขอบถูกเน้นด้วยสีแดงในขั้นตอนนี้ ได้แก่BCเพราะจะก่อให้เกิดวงBCE , DEเพราะจะก่อให้เกิดวงDEBAและFEเพราะจะก่อให้เกิดวงFEBAD
	ในที่สุด กระบวนการจะสิ้นสุดลงด้วยขอบEGที่มีความยาว 9 และพบต้นไม้แผ่คลุมขั้นต่ำ

หลักฐานยืนยันความถูกต้อง

การพิสูจน์ประกอบด้วยสองส่วน ส่วนแรก พิสูจน์ว่าอัลกอริทึมสร้างต้นไม้แผ่คลุม (spanning tree ) ส่วนที่สอง พิสูจน์ว่าต้นไม้แผ่คลุมที่สร้างขึ้นมีน้ำหนักน้อยที่สุด

ต้นไม้ที่ทอดข้าม

อนุญาต $G$ เป็นกราฟที่เชื่อมต่อกันและมีน้ำหนัก และให้ $Y$ เป็นกราฟย่อยของ $G$ สร้างขึ้นโดยอัลกอริทึม $Y$ ไม่สามารถมีวงจรได้ เนื่องจากตามนิยามแล้ว จะไม่มีการเพิ่มขอบหากขอบนั้นทำให้เกิดวงจร $Y$ ไม่สามารถตัดการเชื่อมต่อได้ เนื่องจากขอบแรกที่พบซึ่งเชื่อมต่อส่วนประกอบสองส่วนของ $Y$ ซึ่งจะถูกเพิ่มเข้ามาโดยอัลกอริทึม ดังนั้น $Y$ เป็นต้นไม้แผ่ขยายของ $G$ .

ความเรียบง่าย

เราแสดงให้เห็นว่าข้อเสนอ Pต่อไปนี้เป็นจริงโดยใช้การอุปมาน : ถ้าFคือเซตของขอบที่ถูกเลือกในขั้นตอนใดๆ ของอัลกอริทึมแล้ว จะมีต้นไม้แผ่คลุมขั้นต่ำบางต้นที่ประกอบด้วยFและไม่มีขอบใดๆ ที่ถูกปฏิเสธโดยอัลกอริทึม

เห็นได้ชัดว่าPเป็นจริงในตอนเริ่มต้น เมื่อFว่างเปล่า: ต้นไม้แผ่คลุมขั้นต่ำใดๆ ก็ใช้ได้ และมีอยู่จริงเพราะกราฟเชื่อมต่อแบบมีน้ำหนักจะมีต้นไม้แผ่คลุมขั้นต่ำเสมอ
สมมติว่าP เป็นจริงสำหรับ เซต ขอบ Fที่ไม่ใช่เซตสุดท้ายและให้Tเป็นต้นไม้แผ่คลุมขั้นต่ำที่ประกอบด้วยF
- ถ้าขอบถัดไปที่เลือกeอยู่ในT ด้วย แล้วPจะเป็นจริงสำหรับF + e
- มิฉะนั้น ถ้าeไม่อยู่ในTแล้วT + eจะมีวงจรCวงจรCประกอบด้วยขอบที่ไม่เป็นส่วนหนึ่งของ F + eเนื่องจากeไม่ก่อให้เกิดวงจรเมื่อเพิ่มเข้าไปในFแต่ก่อให้เกิดวงจรในTให้fเป็นขอบที่อยู่ในCแต่ไม่อยู่ในF + eสังเกตว่าfก็เป็นส่วนหนึ่งของT ด้วย เนื่องจากfเป็นส่วนหนึ่งของT + eแต่ไม่อยู่ ใน F + eจาก P fจึงไม่ได้ถูกพิจารณาโดยอัลกอริทึม ดังนั้น fต้องมีน้ำหนักอย่างน้อยเท่ากับeจากนั้นT − f + eจะเป็นต้นไม้ และมีน้ำหนักเท่ากันหรือน้อยกว่าTอย่างไรก็ตาม เนื่องจากTเป็นต้นไม้แผ่คลุมขั้นต่ำ ดังนั้นT − f + e จึง มีน้ำหนักเท่ากับTมิฉะนั้นจะเกิดข้อขัดแย้งและTจะไม่ใช่ต้นไม้แผ่คลุมขั้นต่ำ ดังนั้นT − f + e จึง เป็นต้นไม้แผ่คลุมขั้นต่ำที่ประกอบด้วยF + eและP ก็ เป็นจริง อีกครั้ง
ดังนั้น โดยหลักการอุปมานPจะเป็นจริงเมื่อFกลายเป็นต้นไม้แผ่คลุม ซึ่งจะเป็นไปได้ก็ต่อเมื่อFเป็นต้นไม้แผ่คลุมขั้นต่ำ เท่านั้น

อัลกอริทึมแบบขนาน

อัลกอริทึมของ Kruskal นั้นเป็นแบบลำดับโดยเนื้อแท้และยากที่จะทำให้เป็นแบบขนาน อย่างไรก็ตาม เป็นไปได้ที่จะทำการเรียงลำดับขอบเริ่มต้นแบบขนาน หรืออีกทางหนึ่งคือใช้การใช้งานแบบขนานของฮีปไบนารีเพื่อดึงขอบที่มีน้ำหนักน้อยที่สุดในแต่ละรอบ^{[ 5 ]} เนื่องจากการเรียงลำดับแบบขนานเป็นไปได้ในเวลา $O(n)$ บน $O(\log n)$ โปรเซสเซอร์^{[ 6 ]}เวลาการทำงานของอัลกอริทึมของ Kruskal สามารถลดลงเหลือO ( E α( V )) โดยที่ α อีกครั้งคือฟังก์ชันผกผันของ ฟังก์ชัน Ackermannค่าเดียว

อัลกอริทึม Kruskal รูปแบบหนึ่งที่เรียกว่า Filter-Kruskal ได้รับการอธิบายโดย Osipov et al. ^{[ 7 ]}และเหมาะสมกว่าสำหรับการประมวลผลแบบขนาน แนวคิดพื้นฐานของ Filter-Kruskal คือการแบ่งขอบในลักษณะเดียวกับquicksortและกรองขอบที่เชื่อมต่อจุดยอดของต้นไม้เดียวกันออกเพื่อลดต้นทุนในการเรียงลำดับรหัสเทียม ต่อไปนี้ แสดงให้เห็นถึงสิ่งนี้

ฟังก์ชัน filter_kruskal(G) คือถ้า |GE| < kruskal_threshold: ให้คืนค่า kruskal(G) pivot = choose_random(GE) E  , E  = partition(GE, pivot) A = filter_kruskal(E  ) E  = ตัวกรอง(E  ) A = A ∪ filter_kruskal(E  ) ส่งคืน A ฟังก์ชัน partition(E, pivot) คือ E  = ∅, E  = ∅ สำหรับแต่ละ (u, v) ใน E ถ้า weight(u, v) ≤ pivot แล้ว E  = E  ∪ {(u, v)} มิฉะนั้น E  = E  ∪ {(u, v)} ส่งคืน E  , E ฟังก์ชัน filter(E) คือ E  = ∅ สำหรับแต่ละ (u, v) ใน E ทำซ้ำถ้า find_set(u) ≠ find_set(v) แล้ว E  = E  ∪ {(u, v)} ส่งคืน E

Filter-Kruskal เหมาะกับการประมวลผลแบบขนานมากกว่า เนื่องจากสามารถดำเนินการเรียงลำดับ กรอง และแบ่งพาร์ติชันได้อย่างง่ายดายแบบขนานโดยการกระจายขอบระหว่างโปรเซสเซอร์^{[ 7 ]}

สุดท้ายนี้ ได้มีการสำรวจรูปแบบอื่นๆ ของการใช้งานแบบขนานของอัลกอริทึมของ Kruskal ตัวอย่างเช่น แผนการที่ใช้เธรดช่วยเหลือเพื่อลบขอบที่ไม่ใช่ส่วนหนึ่งของ MST ในเบื้องหลัง^{[ 8 ]}และรูปแบบที่เรียกใช้อัลกอริทึมแบบลำดับบน กราฟย่อย pจากนั้นรวมกราฟย่อยเหล่านั้นจนเหลือเพียงหนึ่งเดียว ซึ่งก็คือ MST สุดท้าย^{[ 9 ]}

ดูเพิ่มเติม

ลิงก์ภายนอก

ข้อมูลสำหรับ ตัวอย่างในบทความ
โค้ดต้นฉบับ ของปลั๊กอิน Gephi สำหรับคำนวณ Minimum Spanning Tree
อัลกอริทึมของครัสกัล พร้อมตัวอย่างและโปรแกรมในภาษาซี++
โค้ดอัลกอริธึมของครัสกัลในภาษา C++ ที่นำไปใช้กับตัวเลขสุ่ม
โค้ดอัลกอริธึมของครัสกัลในภาษา Python พร้อมคำอธิบาย
โค้ดอัลกอริธึมของครัสกัลในภาษาซี พร้อมคำอธิบายและตัวอย่าง
การนำอัลกอริทึมของ Kruskal มาใช้เพื่อหาต้นไม้แผ่คลุมน้อยที่สุดในกราฟ
การวิเคราะห์เปรียบเทียบประสิทธิภาพของอัลกอริธึม Kruskal และ Prim MST

[ 1 ]

[ 3 ]

4 ] อั

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]