อัลกอริธึม Spanning Tree ขั้นต่ำของ Prim

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

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

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

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

อินพุตและเอาต์พุต

Input:รายการที่อยู่ติดกัน:ผลลัพธ์:(0)---(1|1) (0)---(2|3 ) (0)---(3|4)(1)---(0|1) (1)---(4|2)(2)---(0|3)(3)-- -(0|4)(4)---(1|2) (4)---(5|2)(5)---(4|2) (5)---(6|3) (6)---(5|3)

อัลกอริทึม

prims(g:Graph, t:tree, start)

อินพุต - กราฟ g ต้นไม้เปล่า และยอดของเมล็ดชื่อ 'เริ่มต้น'

ผลลัพธ์ − ต้นไม้หลังจากเพิ่มขอบ

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

ตัวอย่าง

#include#define V 7#define INF 999using เนมสเปซ std;//เมทริกซ์ต้นทุนของ graphint 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;class Tree { int n; ขอบขอบ[V-1]; // เนื่องจากต้นไม้มีจุดยอด -1 ขอบสาธารณะ:ต้นไม้ () { 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; //ลบ v จาก unusedVertex tr.addEdge(ed); usedVert[p] =ed.u; พี++; // เพิ่ม u ไปที่ usedVertex }}main() { Tree tr; ไพรม์(tr, 0); //เริ่มต้นโหนด 0 tr.printEdges();}

ผลลัพธ์