DAA - Spanning Tree

ก spanning tree เป็นส่วนย่อยของกราฟที่ไม่มีทิศทางที่มีจุดยอดทั้งหมดเชื่อมต่อกันด้วยจำนวนขอบขั้นต่ำ

หากจุดยอดทั้งหมดเชื่อมต่อกันในกราฟแสดงว่ามีต้นไม้ทอดอยู่อย่างน้อยหนึ่งต้น ในกราฟอาจมีต้นไม้ที่ทอดมากกว่าหนึ่งต้น

คุณสมบัติ

ต้นไม้ที่ทอดไม่มีวัฏจักรใด ๆ
จุดยอดใด ๆ สามารถเข้าถึงได้จากจุดยอดอื่น ๆ

ตัวอย่าง

ในกราฟต่อไปนี้ขอบที่ไฮไลต์จะกลายเป็นต้นไม้ที่ทอดยาว

ต้นไม้ระยะขั้นต่ำ

ก Minimum Spanning Tree (MST)คือส่วนย่อยของขอบของกราฟที่ไม่ได้กำหนดทิศทางแบบถ่วงน้ำหนักที่เชื่อมต่อซึ่งเชื่อมต่อจุดยอดทั้งหมดพร้อมกับน้ำหนักขอบรวมขั้นต่ำที่เป็นไปได้ ในการรับ MST สามารถใช้อัลกอริทึมของ Prim หรืออัลกอริทึมของ Kruskal ได้ ดังนั้นเราจะพูดถึงอัลกอริทึมของ Prim ในบทนี้

ดังที่เราได้กล่าวไปแล้วกราฟหนึ่งเส้นอาจมีต้นไม้ทอดมากกว่าหนึ่งต้น ถ้ามีn จำนวนจุดยอดต้นไม้ที่ทอดควรมี n - 1จำนวนขอบ ในบริบทนี้หากแต่ละขอบของกราฟมีความสัมพันธ์กับน้ำหนักและมีต้นไม้ทอดมากกว่าหนึ่งอันเราจำเป็นต้องหาต้นไม้ที่มีระยะทอดต่ำสุดของกราฟ

ยิ่งไปกว่านั้นหากมีขอบถ่วงน้ำหนักที่ซ้ำกันกราฟอาจมีต้นไม้ที่มีระยะการทอดขั้นต่ำหลายอัน

ในกราฟด้านบนเราได้แสดงต้นไม้ที่ทอดแล้วแม้ว่าจะไม่ใช่ต้นไม้ที่มีระยะทอดขั้นต่ำ ต้นทุนของต้นไม้ที่ทอดนี้คือ (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38

เราจะใช้อัลกอริทึมของ Prim เพื่อค้นหาต้นไม้ที่มีการขยายน้อยที่สุด

อัลกอริทึมของ Prim

อัลกอริทึมของ Prim เป็นวิธีการที่ละโมบในการค้นหาต้นไม้ที่มีระยะทอดน้อยที่สุด ในอัลกอริทึมนี้เพื่อสร้าง MST เราสามารถเริ่มต้นจากจุดยอดโดยพลการ

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

ฟังก์ชัน Extract-Min จะส่งกลับจุดยอดพร้อมต้นทุนขอบขั้นต่ำ ฟังก์ชันนี้ทำงานบน min-heap

ตัวอย่าง

การใช้อัลกอริทึมของ Prim เราสามารถเริ่มต้นจากจุดยอดใดก็ได้ให้เราเริ่มจากจุดยอด 1.

จุดยอด 3 เชื่อมต่อกับจุดยอด 1 ด้วยต้นทุนขอบขั้นต่ำจึงได้เปรียบ (1, 2) จะถูกเพิ่มไปยังต้นไม้ที่ทอดยาว

ถัดไปขอบ (2, 3) ถือว่าเป็นขั้นต่ำของขอบ {(1, 2), (2, 3), (3, 4), (3, 7)}.

ในขั้นตอนต่อไปเราจะได้เปรียบ (3, 4) และ (2, 4)ด้วยต้นทุนขั้นต่ำ ขอบ(3, 4) ถูกเลือกแบบสุ่ม

ในทำนองเดียวกันขอบ (4, 5), (5, 7), (7, 8), (6, 8) และ (6, 9)ถูกเลือก เมื่อมีการเยี่ยมชมจุดยอดทั้งหมดตอนนี้อัลกอริทึมจะหยุดลง

ต้นทุนของต้นไม้ทอดคือ (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23 ไม่มีต้นไม้ทอดอีกต่อไปในกราฟนี้ที่มีต้นทุนน้อยกว่า 23.