ในบทความนี้ เราจะทำความเข้าใจความแตกต่างระหว่าง Prim's และ Kruskal's algorithms
Kruskal's Algorithm สำหรับ Minimum Spanning Tree (MST)
- เมื่อมีกราฟที่เชื่อมต่อและไม่มีทิศทาง (undirected) spanning tree ของกราฟดังกล่าวคือ subgraph ที่เป็นต้นไม้เชื่อมโยงทุก vertex
- กราฟเดียวสามารถมี spanning trees หลายตัวได้
- Minimum spanning tree (MST) (หรือ minimum weight spanning tree) สำหรับกราฟที่มีน้ำหนัก เชื่อมต่อ และไม่มีทิศทาง คือ spanning tree ที่มีน้ำหนักน้อยกว่าหรือเท่ากับน้ำหนักของทุก spanning tree อื่น
- น้ำหนักของ spanning tree กำหนดโดยการบวกน้ำหนักที่เกี่ยวข้องกับทุก edge ของ spanning tree
- MST สามารถสร้างจาก vertex ที่มีน้ำหนักน้อยที่สุดในกราฟ
- แต่ละโหนดถูกท่องเพียงครั้งเดียว
- ทำงานเร็วใน sparse graphs
- Time complexity คือ O(E log V) โดย V คือจำนวน vertices
- ทำงานกับ disconnected components ได้
ขั้นตอนการหา MST ด้วย Kruskal's Algorithm:
- จัดเรียง edges ตามลำดับน้ำหนักจากน้อยไปมาก
- เลือก edge ที่เล็กที่สุด
- ตรวจสอบว่ามันสร้าง cycle กับ spanning-tree ที่สร้างขึ้นจนถึงจุดนั้นหรือไม่
- หากยังไม่สร้าง cycle ต้องรวม edge นี้เข้าไป
- มิฉะนั้น สามารถทิ้งได้
- ทำซ้ำขั้นตอน 2,3,4 จนกว่า spanning tree จะมี V-1 edges
Prim's Algorithm สำหรับ Minimum Spanning Tree (MST)
- คล้ายกับ Kruskal's algorithm กล่าวคือ เป็น greedy algorithm
- เริ่มต้นด้วย spanning tree ว่าง รักษาชุด vertex สองชุด
- ชุดแรกมี vertices ที่รวมอยู่ใน MST แล้ว ส่วนอีกชุดมี vertices ที่ยังไม่รวม
- ในทุกขั้นตอน อัลกอริทึมพิจารณา edges ทั้งหมดที่จะเชื่อมสองชุด เลือก edge ที่มีน้ำหนักน้อยที่สุด
- หลังจากขั้นตอนนี้ อัลกอริทึมย้ายไปยัง endpoint อีกด้านของ edge ของชุดที่มี MST
- MST สามารถสร้างจาก vertex ใดก็ได้ในกราฟ
- โหนดหนึ่งถูกเดินทางหลายครั้งเพื่อหาค่าระยะทางต่ำสุด
- Time complexity คือ O(V²) โดย V คือจำนวน vertices สามารถปรับปรุงเป็น O(E + log V) ด้วย Fibonacci heaps
- ทำงานเร็วใน dense graphs
- ให้ connected components และทำงานกับ connected graph เท่านั้น
ขั้นตอนการหา MST ด้วย Prim's Algorithm:
- สร้าง mstSet ที่ติดตาม vertices ที่รวมอยู่ใน MST แล้ว
- กำหนด key value ให้ทุก vertices ของ input graph
- Key values เริ่มต้นกำหนดเป็น 'INFINITE'
- กำหนด key value 0 ให้ vertex แรกเพื่อถูกเลือกก่อน
- เมื่อ mstSet ยังไม่รวม vertices ทั้งหมด ทำตามขั้นตอนด้านล่าง
- เลือก vertex 'u' ที่ไม่อยู่ใน mstSet และมี key value ต่ำสุด
- 'u' นี้ถูกรวมเข้า mstSet
- อัปเดต key value ของ vertices ติดจำนวนทั้งหมดของ 'u'
- ทำได้โดย iteration ผ่าน vertices ติดจำนวนทั้งหมด
- สำหรับ vertex ติดจำนวน 'v' หากน้ำหนัก edge 'u'-'v' น้อยกว่า key value ก่อนหน้าของ 'v' ให้อัปเดต key value เป็นน้ำหนักของ 'u-v'
