ในโพสต์นี้ เราจะเข้าใจความแตกต่างระหว่างอัลกอริธึมของ Prim และ Kruskal
อัลกอริทึมของ Kruskal สำหรับ Mininum Spanning Tree (MST)
- เมื่อให้กราฟที่เชื่อมต่อและไม่มีทิศทาง ต้นไม้ขยายของกราฟดังกล่าวคือกราฟย่อย ซึ่งเป็นต้นไม้ที่เชื่อมจุดยอดทั้งหมด
- กราฟเดียวสามารถมีต้นไม้ทอดยาวได้หลายต้น
- แผนภูมิที่ทอดข้ามขั้นต่ำ (MST) (หรือเรียกอีกอย่างว่าแผนภูมิขยายน้ำหนักขั้นต่ำ) สำหรับกราฟที่ถ่วงน้ำหนัก เชื่อมต่อและไม่มีทิศทางคือแผนภูมิแบบขยายที่มีน้ำหนักน้อยกว่าหรือเท่ากับน้ำหนักของแผนภูมิที่ทอดข้ามต้นไม้อื่นๆ ทุกต้น
- น้ำหนักของต้นไม้ขยายจะกำหนดโดยการเพิ่มน้ำหนักที่เกี่ยวข้องกับทุกขอบของต้นไม้ที่ขยาย
- สร้างแผนผังระยะห่างขั้นต่ำได้จากจุดยอดที่มีน้ำหนักต่ำสุดในกราฟ
- โหนดหนึ่งถูกสำรวจเพียงครั้งเดียว
- ทำงานได้อย่างรวดเร็วในกราฟที่กระจัดกระจาย
- ความซับซ้อนของเวลาคือ O(E log V) โดยที่ V คือจำนวนจุดยอด
- มันสามารถทำงานกับส่วนประกอบที่ไม่ได้เชื่อมต่อได้เช่นกัน
ขั้นตอนในการค้นหา MST โดยใช้อัลกอริทึมของ Kruskal:
- เรียงลำดับขอบจากน้อยไปมากจากน้ำหนักที่เกี่ยวข้อง
- เลือกขอบที่เล็กที่สุด
- ตรวจดูว่าเกิดวงรอบกับต้นไม้ขยายที่ก่อตัวขึ้นจนถึงจุดนั้นหรือไม่
- ถ้าวัฏจักรไม่ได้เกิดขึ้น ก็ต้องรวมขอบนี้ด้วย
- มิฉะนั้นก็ทิ้งได้
- ทำซ้ำขั้นตอนที่ 2,3,4 จนกว่าต้นไม้ขยายจะมีขอบ V-1
อัลกอริธึมของ Prim Mininum Spanning Tree (MST)
- สิ่งนี้คล้ายกับอัลกอริทึมของ Kruskal นั่นคือมันเป็นอัลกอริทึมที่โลภ
- มันเริ่มต้นด้วยต้นไม้ที่ทอดยาวว่างเปล่า รักษาจุดยอดสองชุดไว้
- ชุดแรกจะมีจุดยอดที่รวมอยู่ใน MST แล้ว ในขณะที่ชุดอื่นๆ จะมีจุดยอดที่ยังไม่ได้รวมไว้
- ในทุกขั้นตอน อัลกอริธึมจะพิจารณาขอบทั้งหมดที่จะเชื่อมต่อทั้งสองชุด จากนั้นจะเลือกขอบน้ำหนักขั้นต่ำจากขอบเหล่านี้
- หลังจากขั้นตอนนี้ อัลกอริทึมจะย้ายไปยังจุดสิ้นสุดอื่นของขอบของชุดที่มี MST
- สร้างแผนผังระยะห่างขั้นต่ำจากจุดยอดใดก็ได้ในกราฟ
- โหนดหนึ่งเดินทางหลายครั้งเพื่อให้ได้ค่าระยะทางต่ำสุด
- มันมีความซับซ้อนของเวลาของ O(V2) โดยที่ V คือจำนวนจุดยอด ความซับซ้อนในครั้งนี้สามารถเพิ่มเป็น O(E + log V) ได้โดยใช้ Fibonacci heaps
- ทำงานได้อย่างรวดเร็วในกราฟหนาแน่น
- ให้ส่วนประกอบที่เชื่อมต่อ และใช้งานได้กับกราฟที่เชื่อมต่อเท่านั้น
ขั้นตอนในการค้นหา MST โดยใช้อัลกอริทึมของ Prim:
- มีการสร้าง mstSet ซึ่งติดตามจุดยอดที่รวมอยู่ใน MST แล้ว
- ค่าคีย์ถูกกำหนดให้กับจุดยอดทั้งหมดของกราฟอินพุต
- ค่าคีย์ถูกกำหนดในขั้นต้นเป็น 'INFINITE'
- ค่าคีย์ 0 ถูกกำหนดให้กับจุดยอดแรกเพื่อให้เลือกได้ก่อน
- เมื่อ mstSet ไม่รวมจุดยอดทั้งหมด จะมีการปฏิบัติตามขั้นตอนด้านล่าง
- มีการเลือกจุดยอด 'u' ซึ่งไม่มีอยู่ใน mstSet และยังมีค่าคีย์ขั้นต่ำอีกด้วย
- ตอนนี้ 'u' รวมอยู่ใน mstSet แล้ว
- ค่าคีย์ของจุดยอดที่อยู่ติดกันทั้งหมดของ 'u' ได้รับการอัปเดตแล้ว
- สามารถทำได้โดยการวนซ้ำจุดยอดที่อยู่ติดกันทั้งหมด
- สำหรับทุกจุดยอดที่อยู่ติดกัน 'v' หากน้ำหนักของขอบ 'u'-'v' น้อยกว่าค่าคีย์ก่อนหน้าของ 'v' ค่าคีย์จะได้รับการอัปเดตเป็นน้ำหนักของ 'u-v '.
