ต้นไม้ทอดข้าม (Spanning Trees)

ต้นไม้ทอดข้าม (Spanning Trees)

ต้นไม่ (Tree) เป็นเซตย่อย (Subset) ของกราฟไม่มีทิศทาง ดังนั้นเราจึงสามารถสร้างต้นไม้จากกราฟได้ กราฟที่จะนำมาสร้างต้นไม้ จะต้องเชื่อมต่อกัน (Connected) ส่วนต้นไม้ที่ได้จะต้องประกอบด้วยทุกเวอร์เทกซ์จากกราฟ โหนดในต้นไม้ต้องเชื่อมต่อกัน และต้องไม่เป็นวง (Acyclic) ต้นไม้ที่สร้างจากกราฟนี้เรียกว่า ต้นไม้ทอดข้าม (Spanning Tree)

ต้นไม้ทอดข้ามน้อยสุด (Minimum Spanning Trees)

จากตัวอย่างข้างต้นจะเห็นว่า เราสามารถสร้างต้นไม้ทอดข้ามจากกราฟได้หลายต้น แต่ที่อยู่ในความสนใจคือ กรณ๊ที่สร้างต้นไม้ทอดข้ามจากกราฟแบบมีน้ำหนัก (Weighted Graph) โดยให้มีน้ำหนักรวมของเอดจ์น้อยที่สุด ซึ่งเราเรียกต้นไม้นี้ว่า ต้นไม้ทอดข้ามน้อยสุด (Minimum Spaning Tree)

อัลกอริทึมของพริม (Prim’s Algorithm)

อัลกอริทึมของพริมใช้วิธีการเชิงละโมบเช่นเดียวกับอัลกอริทึมของดิจสตราโดยเริ่มต้นจาก

เวอร์เทกซ์ที่กำหนดแล้วหาเวอร์เทกข้างเคียง เรียงตามค่าน้ำหนักของเอดจ์โดยใช้ Priority Queue เลือกเวอร์เทกซ์ที่มีค่าน้ำหนักของเอดจ์น้อยที่สุด แล้วหาเวอร์เทกซ์ข้างเคียงของเวอร์เทกซ์นี้ใส่ไว้ใน Priority Queue ทำอย่างนี้ไปเรื่อย ๆ จนครบทุกเวอร์เทกซ์

ซึ่งแนวทางข้างต้นสามารถนำมาเขียนเป็นอัลกอริทึมได้ดังนี้

initMarks (graph)

clearPriorityQ (pqueue)

enPQ (pqueue, startVertex)

do

dePQ (pqueue, vertex)

if (NOT vertexMarked)

markVertex (vertex)

getAdjacencyVertices (adjList)

enPQ (pqueue, adjList)

while (NOT emptyPQ (pqueue))

จะเห็นได้ว่าอัลกอริทึมของพริม เพื่อหาต้นไม้ทอดข้ามน้อยที่สุดเกือบเหมือนอัลกอริทึมเพื่อหาเส้นทางสั้นที่สุดทุกประการ แต่ในการหาเส้นทางที่สั้นที่สุด ต้องปรับน้ำหนัก (updateWeiht) ในขณะที่การหาต้นไม้ทอดข้ามน้อยที่สุดไม่ต้อง

วิธีการสร้างต้นไม้ทอดข้ามน้อยสุด

ตัวอย่างการสร้าต้นไม้ทอดข้ามน้อยสุด จากกราฟที่กำหนดให้ โดยเริ่มจากเวอร์เทกซ์ A

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s