FANDOM


Q
Prim’s Algorithm

การทำงานของ Prim's algorithm จะเพิ่ม edge เข้าไปใน A ทีละedgeเพื่อสร้าง tree เพียงต้นเดียว การทำงานจะเริ่ม จากการกำหนด vertex r เป็น root แล้วขยาย treeไปเรื่อยๆ จน span ทุก vertices V ในแต่ละขั้นตอน light edge ที่เชื่อมระหว่าง vertex ใน A และ vertex ใน V-A จะถูกเพิ่มเข้าไปใน tree เมื่อการทำงานสิ้นสุด edges ใน A จะ ประกอบกันเป็น Minimum Spanning Tree Prim 's algorithm เป็น greedy algorithm เพราะในแต่ละขั้นตอน จะมีการเพิ่ม edge ที่น้อยที่สุด เข้าไปใน tree ข้อดี ของ Prim's algorithm คือความง่ายในการเลือก edge เ พื่อเพิ่มเข้าไปใน Aเมื่อเริ่มการทำงาน ทุก vertices จะอยู่ใน priority queue Q ซึ่งจัดเรียงตาม keyสำหรับแต่ละ vertex v (ที่ไม่อยู่ใน A) - key[v] คือ edge ที่มี weight ที่น้อยที่สุด ที่เชื่อม vertex v กับparent ของ v ใน A และ ถ้าไม่มี edge (v ไม่ได้เชื่อมต่อกับvertex ใด) key[v] = ∞ - ¶(v) จะให้ค่า parent ของ v ใน A ในระหว่างการทำงาน A (MST) จะถูกอยู่ในรูปแบบ A = {(v, ¶(v) : v ∈ V – {r} - Q ) } และเมื่อการทำงานสิ้นสุด Q จะว่าง และ A (MST) สำหรับ G จะเป็น A = {(v, ¶(v) : v ∈ V – {r}) }

ตัวอย่าง

Untitled

Prim’s Algorithm บรรทัด 1 นำทุก Vertices บรรจุใน Q บรรทัด 2-3 กำหนดให้ key ของทุก vertices เป็น (ยังไม่มีการเชื่อมต่อ) บรรทัด 4 กำหนดให้ key ของ vertex r (root) เป็น 0 บรรทัด 5 กำหนดให้ parent ของ vertex r (root) เป็น NIL (root ไม่มี parent) ซึ่งจะ เป็นการย้าย root ออกจาก Q หลักการคือ จะเป็นการแบ่ง vertices เป็น 2 กลุ่ม คือ Q และ V – Q (A) ซึ่งหลังจากนี้จะย้าย vertex จาก Q นำไปสร้าง tree ใน V-Q ทีละ vertex บรรทัด 7 ย้าย vertex u ใน Q ที่มี parent เป็น vertex ล่าสุด ใน V-Q และมี weight ที่น้อยที่สุด ออกจาก Q นำไปสร้างเป็น edge ใน V-Q เป็นการนำ light edge ที่ข้ามเส้นตัด (Q,V-Q) เพิ่มเข้าไปใน tree บรรทัด 8-11 update ทุกๆ vertices v ใน Q ที่ adjacent กับ u ใน V-Q โดย key[v] = w(v, ¶(v)) และ ¶(v) = u





ประสิทธิภาพของ Prim's algorithm ขึ้นกับการโครงสร้างข้อมูล ที่ใช้กับ priority Queue Q ถ้า Q มีโครงสร้างเป็น binary heap ถ้าใช้ BUILD-HEAP procedure การกำหนดค่าเริ่มต้น บรรทัด 1 -4 จะใช้เวลา O(V) และในส่วนของการวนรอบ บรรทัด 5 - 11 จะทำซ้ำ |V| ครั้ง และ EXTRACT_MIN ใช้เวลา O(lgV) ดังนั้นการเรียก XTRACT_MIN ทั้งหมดจะใช้เวลา O(VlogV) และในส่วน FOR loop จะมีการทำซ้ำ O(E) ครั้ง เพราะเป็นการ รวมความยาวของทุก adjacent list ซึ่งใช้เวลา 2|E| ภายใน FOR loop การตรวจสอบว่าเป็นสมาชิก ใน Q หรือไม่ (บรรทัด 9) จะใช้เวลาคงที่ การกำหนดค่า (บรรทัด 11) จะเกี่ยวข้อง กับการ DECREASE-KEY ใน heap ซึ่งใช้เวลา O(lgV) total running time ของ Prim's algorithm คือ O(VlgV + Elgv) = O(ElgV)


Running time ของ Prim's algorithm สามารถปรับปรุงให้ดีขึ้น ได้โดยใช้ Fibonacci heaps ถ้า vertices จำนวน |V| ถูกเก็บใน Fibonacci heaps การทำ EXTRACT-MIN จะใช้เวลา O(lgV) และ การทำ DECREASE-KEY (บรรทัด 11) จะใช้เวลา O(1) ดังนั้นถ้าเราใช้ Fibonacci heaps กับ priority queue Q total running time ของ Prim's algorithm จะกลายเป็น O(E + VlogV)