อัลกอริธึมของ Prim เป็นอัลกอริธึมที่โลภที่ค้นหาแผนผังการแผ่ขยายขั้นต่ำสำหรับกราฟแบบไม่มีทิศทางแบบถ่วงน้ำหนัก โดยจะค้นหาส่วนย่อยของขอบที่สร้างต้นไม้ที่มีจุดยอดทุกจุด โดยจะลดน้ำหนักรวมของขอบทั้งหมดในต้นไม้ให้น้อยที่สุด
อัลกอริธึมทำงานโดยการสร้างทรีนี้ทีละจุด จากจุดยอดเริ่มต้นตามอำเภอใจ ในแต่ละขั้นตอนโดยเพิ่มการเชื่อมต่อที่ถูกที่สุดจากทรีไปยังอีกจุดยอด
อัลกอริทึมของ Prim ทำงานอย่างไร
เรามาดูภาพประกอบว่าอัลกอริธึมของ Prim ทำงานอย่างไร -
1. เลือกโหนดใดก็ได้เป็นโหนดรูท:ในกรณีนี้ เราเลือกโหนด S เป็นโหนดรูทของแผนผังการขยายของ Prim โหนดนี้ถูกเลือกโดยพลการ ดังนั้นโหนดใดๆ ก็สามารถเป็นโหนดรูทได้ บางคนอาจสงสัยว่าเหตุใดวิดีโอใดๆ จึงสามารถเป็นโหนดรูทได้ ดังนั้น คำตอบคือ ในแผนผังที่ขยาย โหนดทั้งหมดของกราฟจะรวมอยู่ด้วย และเนื่องจากมันเชื่อมต่อกัน จึงต้องมีขอบอย่างน้อยหนึ่งด้าน ซึ่งจะเชื่อมต่อกับส่วนที่เหลือของแผนภูมิ
2. ตรวจสอบขอบขาออกและเลือกขอบที่มีต้นทุนน้อยกว่า:หลังจากเลือกโหนดราก S เราจะเห็นว่า S, A และ S, C เป็นสองขอบที่มีน้ำหนัก 7 และ 8 ตามลำดับ เราเลือกขอบ S, A เนื่องจากมีค่าน้อยกว่าขอบอื่น
ตอนนี้ ต้นไม้ S-7-A ถือเป็นโหนดเดียว และเราตรวจสอบขอบทั้งหมดที่อยู่นอกโหนด เราเลือกอันที่มีต้นทุนต่ำที่สุดและรวมไว้ในแผนผัง
หลังจากขั้นตอนนี้ ต้นไม้ S-7-A-3-C จะถูกสร้างขึ้น ตอนนี้ เราจะถือว่ามันเป็นโหนดอีกครั้ง และจะตรวจสอบขอบทั้งหมดอีกครั้ง อย่างไรก็ตาม เราจะเลือกความได้เปรียบด้านต้นทุนที่น้อยที่สุดเท่านั้น ในกรณีนี้ C-3-D เป็นขอบใหม่ ซึ่งน้อยกว่าราคาขอบอื่นๆ 8, 6, 4 และอื่นๆ
หลังจากเพิ่มโหนด D สำหรับต้นไม้ที่ทอดยาว ตอนนี้เรามีขอบสองด้านที่ยื่นออกมาโดยมีค่าใช้จ่ายเท่ากัน นั่นคือ D-2-T และ D-2-B ดังนั้น เราสามารถเพิ่มอันใดอันหนึ่งได้ แต่ขั้นตอนต่อไปจะทำให้ได้ขอบ 2 อีกครั้งเนื่องจากมีต้นทุนน้อยที่สุด ดังนั้นเราจึงแสดงต้นไม้ที่ทอดยาวพร้อมทั้งขอบทั้งสองข้าง
ตอนนี้เรามาดูกันว่าเราจะใช้โค้ดของเราได้อย่างไร -
ตัวอย่าง
primsMST() {
// Initialize graph that'll contain the MST
const MST = new Graph();
if (this.nodes.length === 0) {
return MST;
}
// Select first node as starting node
let s = this.nodes[0];
// Create a Priority Queue and explored set
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
let explored = new Set();
explored.add(s);
MST.addNode(s);
// Add all edges from this starting node to the PQ taking weights as priority
this.edges[s].forEach(edge => {
edgeQueue.enqueue([s, edge.node], edge.weight);
});
// Take the smallest edge and add that to the new graph
let currentMinEdge = edgeQueue.dequeue();
while (!edgeQueue.isEmpty()) {
// COntinue removing edges till we get an edge with an unexplored node
while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
currentMinEdge = edgeQueue.dequeue();
}
let nextNode = currentMinEdge.data[1];
// Check again as queue might get empty without giving back unexplored element
if (!explored.has(nextNode)) {
MST.addNode(nextNode);
MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
// Again add all edges to the PQ
this.edges[nextNode].forEach(edge => {
edgeQueue.enqueue([nextNode, edge.node], edge.weight);
});
// Mark this node as explored explored.add(nextNode);
s = nextNode;
}
}
return MST;
} คุณสามารถทดสอบได้โดยใช้:
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("C", "D", 3);
g.addEdge("D", "E", 8);
g.addEdge("E", "F", 10);
g.addEdge("B", "G", 9);
g.primsMST().display(); ผลลัพธ์
สิ่งนี้จะให้ผลลัพธ์ -
A->B, D B->A, G D->A, C, E C->D E->D, F G->B F->E
โปรดทราบว่ากราฟเริ่มต้นของเราคือ -
ตัวอย่าง
/** * A * / | \ * C | B * \ | | * D G * | / * E * | * F */
ผลลัพธ์
กราฟปัจจุบันของเรามีลักษณะดังนี้ -
/** * A * |\ * C | B * \ | | * D G * | * E * | * F * */
เราได้ลบขอบที่มีราคาแพงที่สุดและตอนนี้ก็มีต้นไม้ที่ทอดยาว
