Prim's (Minimum Spanning Tree) อัลกอริทึม MST

มีกราฟเชื่อมต่อ G(V,E) และน้ำหนักหรือต้นทุนสำหรับทุกขอบ อัลกอริธึมของ Prim จะค้นหาต้นไม้ที่ทอดข้ามขั้นต่ำจากกราฟ G

เป็นแนวทางการปลูกต้นไม้ อัลกอริทึมนี้ต้องการค่าเมล็ดพันธุ์เพื่อเริ่มต้นทรี ยอดของเมล็ดโตจนเกิดเป็นต้นไม้ทั้งหมด

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

• ความซับซ้อนของเวลาของปัญหานี้คือ O(V2) โดยที่ V คือจำนวนจุดยอด

ป้อนข้อมูล − รายการที่อยู่ติดกัน −

เอาท์พุต -

อัลกอริทึม

prims(g:กราฟ, t:tree, start)

ป้อนข้อมูล − กราฟ g ต้นไม้เปล่า และจุดยอดของเมล็ดที่ชื่อ 'start' ผลลัพธ์:ต้นไม้หลังจากเพิ่มขอบแล้ว

Begin กำหนดสองชุดเป็น usedVert, unusedVert usedVert[0] :=start และ unusedVert[0] :=φ สำหรับจุดยอดทั้งหมดยกเว้น start do usedVert[i] :=φ unusedVert[i] :=i //add all จุดยอดในรายการที่ไม่ได้ใช้ทำในขณะที่จำนวนของจุดยอดใน usedVert ≠ V do //V คือจำนวนโหนดทั้งหมด min :=∞ สำหรับจุดยอดทั้งหมดของ usedVert array ทำสำหรับจุดยอดทั้งหมดของกราฟ ถ้า min> cost[i,j] AND ฉัน ≠ j แล้ว min :=cost[i,j] ed :=edge ระหว่าง i และ j และ cost of ed :=min done unusedVert[destination of ed] :=φ เพิ่ม edge ed ลงในทรี t เพิ่มแหล่งที่มาของ แก้ไขเป็น usedVert doneEnd

ตัวอย่าง(C++)

#include#define V 7#define INF 999using เนมสเปซ std;//เมทริกซ์ต้นทุนของกราฟต์ costMat[V][V] ={ {0, 1, 3, 4, INF, 5, INF} , {1, 0, INF, 7, 2, INF, INF}, {3, INF, 0, INF, 8, INF, INF}, {4, 7, INF, 0, INF, INF, INF}, { INF, 2, 8, INF, 0, 2, 4}, {5, INF, INF, INF, 2, 0, 3}, {INF, INF, INF, INF, 4, 3, 0}};typedef struct { int u, v, cost;}edge;คลาสทรี{ int n; ขอบขอบ[V-1]; //ในขณะที่ต้นไม้มีจุดยอด-1 ขอบสาธารณะ:Tree(){ n =0; } เป็นโมฆะ addEdge (ขอบ e) { ขอบ [n] =e; // เพิ่มขอบ e ลงในทรี n++; } โมฆะ printEdges(){ //ขอบพิมพ์ ต้นทุน และต้นทุนรวม int tCost =0; for(int i =0; i costMat[i][j] &&costMat[i][j] !=0){ //ค้นหาขอบด้วยต้นทุนขั้นต่ำ //เช่น u ถูกพิจารณาและ v ยังไม่ถูกพิจารณา min =costMat[i][j]; ed.u =ผม; ed.v =เจ; ed.cost =นาที; } } } } unusedVert[ed.v] =-1;//delete v จาก unusedVertex tr.addEdge(ed); usedVert[p] =ed.u; p++;//เพิ่ม u ไปที่ usedVertex }}main(){ Tree tr; ไพรม์(tr, 0); //เริ่มต้นโหนด 0 tr.printEdges();}

ผลลัพธ์