ในวิทยาการคอมพิวเตอร์อัลกอริทึมของ Primเป็นอัลกอริทึมแบบโลภ (greedy algorithm)ที่ใช้ค้นหาต้นไม้แผ่คลุมน้อยที่สุด (minimum spanning tree ) สำหรับกราฟแบบไม่มีทิศทาง ที่มีน้ำหนัก หมายความว่ามันจะค้นหาส่วนย่อยของขอบที่สร้างเป็นต้นไม้ซึ่งรวมทุกจุดยอดโดยที่น้ำหนักรวมของขอบ ทั้งหมด ในต้นไม้นั้นมีค่าน้อยที่สุด อัลกอริทึมนี้ทำงานโดยการสร้างต้นไม้นี้ทีละจุดยอด จากจุดยอดเริ่มต้นใดๆ ในแต่ละขั้นตอนจะเพิ่มการเชื่อมต่อที่ถูกที่สุดเท่าที่จะเป็นไปได้จากต้นไม้ไปยังจุดยอดอื่น

อัลกอริทึมนี้ได้รับการพัฒนาขึ้นในปี พ.ศ. 2473 โดยนักคณิตศาสตร์ชาว เช็ก Vojtěch Jarník ^{[ 1 ]}และต่อมาได้รับการค้นพบและเผยแพร่อีกครั้งโดย นัก ^{วิทยาศาสตร์}คอมพิวเตอร์Robert C. Primในปี พ.ศ. 2490 ^{[ 2 ]}และEdsger W. Dijkstraในปี พ.ศ. 2492 ^{[ 3 ]}ดังนั้นบางครั้งจึงเรียกว่าอัลกอริทึมของ Jarník [ ^{4 ]}อัลกอริทึม Prim–Jarník [ ^{5 ]}อัลกอริทึม Prim–Dijkstra ^{[ 6 ]} หรือ อั ลก^อริทึม DJP ^{[ 7 ]}

อัลกอริทึมที่รู้จักกันดีอื่นๆ สำหรับปัญหานี้ ได้แก่อัลกอริทึมของ Kruskalและอัลกอริทึมของ Borůvka [ ^{8 ] อั}ลกอริทึมเหล่านี้ค้นหาป่าแผ่ขยายขั้นต่ำในกราฟที่อาจไม่เชื่อมต่อกัน ในทางตรงกันข้าม รูปแบบพื้นฐานที่สุดของอัลกอริทึมของ Prim จะค้นหาต้นไม้แผ่ขยายขั้นต่ำในกราฟที่เชื่อมต่อกันเท่านั้น อย่างไรก็ตาม การเรียกใช้อัลกอริทึมของ Prim แยกกันสำหรับแต่ละส่วนประกอบที่เชื่อมต่อกันของกราฟ ก็สามารถใช้เพื่อค้นหาป่าแผ่ขยายขั้นต่ำได้เช่นกัน^{[ 9 ]}ในแง่ของความซับซ้อนของเวลา เชิงอะซิมโทติก อัลกอริทึมทั้งสามนี้มีความเร็วเท่ากันสำหรับกราฟแบบเบาบางแต่ช้ากว่าอัลกอริทึมที่ซับซ้อนกว่าอื่นๆ^{[ 7 ] [ 6 ]} อย่างไรก็ตาม สำหรับกราฟที่มีความหนาแน่นเพียงพอ อัลกอริทึมของ Prim สามารถทำงานได้ในเวลาเชิงเส้นซึ่งตรงตามหรือปรับปรุงขอบเขตเวลาสำหรับอัลกอริทึมอื่นๆ^{[ 10 ]}

โดยคร่าวๆ อาจอธิบายอัลกอริทึมนี้ได้ว่าดำเนินการตามขั้นตอนต่อไปนี้:

กล่าวโดยละเอียด สามารถนำไปใช้ได้ตามรหัสเทียมด้านล่างนี้

ฟังก์ชัน Prim(vertices, edges) คือสำหรับแต่ละจุดยอดใน vertices ให้ทำซ้ำ cheapestCost[vertex] ← ∞ cheapestEdge[vertex] ← null สำรวจ ← เซตว่าง ยังไม่ได้สำรวจ ← เซตที่ประกอบด้วยจุดยอดทั้งหมด startVertex ← องค์ประกอบใดๆ ของกลุ่มจุดยอด cheapestCost[startVertex] ← 0 ในขณะที่ยังไม่ได้สำรวจนั้นไม่ได้ว่างเปล่า // เลือกจุดยอดในพื้นที่ที่ยังไม่ได้สำรวจโดยใช้ต้นทุนต่ำสุด currentVertex ← vertex in unexplored with minimum cheapestCost[vertex] unexplored.remove(currentVertex) explored.add(currentVertex) สำหรับแต่ละขอบ (currentVertex, neighbor) ใน edges ให้ตรวจสอบว่า neighbor อยู่ใน unexplored และ weight(currentVertex, neighbor) < cheapestCost[neighbor] หรือไม่ cheapestCost[neighbor] ← weight(currentVertex, neighbor) cheapestEdge[neighbor] ← (currentVertex, neighbor) resultEdges ← รายการว่าง สำหรับแต่ละจุดยอดใน vertices ให้ทำดังนี้ถ้า cheapestEdge[vertex] ≠ null แล้ว resultEdges.append(cheapestEdge[vertex]) ผลลัพธ์ขอบ

ดังที่ได้อธิบายไว้ข้างต้น จุดเริ่มต้นของอัลกอริทึมจะถูกเลือกโดยพลการ เนื่องจากรอบแรกของลูปหลักของอัลกอริทึมจะมีชุดของจุดยอดในQที่มีน้ำหนักเท่ากันทั้งหมด และอัลกอริทึมจะเริ่มต้นต้นไม้ใหม่ในF โดยอัตโนมัติ เมื่อสร้างต้นไม้แผ่คลุมของแต่ละส่วนประกอบที่เชื่อมต่อกันของกราฟอินพุตเสร็จสมบูรณ์ อัลกอริทึมอาจถูกปรับเปลี่ยนให้เริ่มต้นด้วยจุดยอดs ใดๆ โดยการตั้งค่าC [ s ] ให้เป็นตัวเลขที่เล็กกว่าค่าอื่นๆ ของC (เช่น ศูนย์) และอาจถูกปรับเปลี่ยนให้ค้นหาต้นไม้แผ่คลุมเพียงต้นเดียวแทนที่จะเป็นป่าแผ่คลุมทั้งหมด (ซึ่งตรงกับคำอธิบายอย่างไม่เป็นทางการมากกว่า) โดยหยุดเมื่อใดก็ตามที่พบจุดยอดอื่นที่ถูกทำเครื่องหมายว่าไม่มีขอบที่เกี่ยวข้อง

อัลกอริทึมรูปแบบต่างๆ จะแตกต่างกันในวิธีการใช้งาน เซต Q : อาจเป็น รายการเชื่อมโยง แบบง่าย หรืออาร์เรย์ของจุดยอด หรืออาจเป็น โครงสร้างข้อมูล คิวลำดับความสำคัญ ที่ซับซ้อนกว่า การเลือกเช่นนี้ส่งผลให้ความซับซ้อนเชิงเวลาของอัลกอริทึมแตกต่างกัน โดยทั่วไปแล้ว คิวลำดับความสำคัญจะค้นหาจุดยอดvที่มีต้นทุนต่ำที่สุดได้เร็วกว่า แต่จะต้องมีการอัปเดตที่แพงกว่าเมื่อค่าของC [ w ] เปลี่ยนแปลง

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

โครงสร้างข้อมูลน้ำหนักขอบขั้นต่ำ	ความซับซ้อนด้านเวลา (โดยรวม)
เมทริกซ์ประชิดการค้นหา	${\displaystyle O(|V|^{2})}$
ฮีปไบนารีและรายการความสัมพันธ์	${\displaystyle O((|V|+|E|)\log |V|)=O(|E|\log |V|)}$
กองฟิโบนาชี่และรายการความสัมพันธ์	${\displaystyle O(|E|+|V|\log |V|)}$

การใช้งานวิธีของ Prim อย่างง่าย โดยใช้เมทริกซ์ประชิดหรือ การแสดงกราฟ รายการประชิดและการค้นหาน้ำหนักขั้นต่ำในอาร์เรย์ของน้ำหนักแบบเชิงเส้นเพื่อหาขอบที่มีน้ำหนักน้อยที่สุดที่จะเพิ่มเข้าไปนั้น ต้องใช้ เวลาในการทำงาน O ( | V | ^² ) อย่างไรก็ตาม เวลาในการทำงานนี้สามารถปรับปรุงได้อย่างมากโดยใช้ฮีปในการค้นหาน้ำหนักขั้นต่ำในลูปภายในของอัลกอริทึม

เวอร์ชันปรับปรุงแรกใช้ฮีปเพื่อจัดเก็บขอบทั้งหมดของกราฟอินพุต โดยเรียงลำดับตามน้ำหนัก ซึ่งทำให้เวลาการทำงานในกรณีที่เลวร้ายที่สุดคือ O(|E| log |E|) แต่การจัดเก็บจุดยอดแทนขอบสามารถปรับปรุงให้ดียิ่งขึ้นไปอีก ฮีปควรเรียงลำดับจุดยอดตามน้ำหนักขอบที่น้อยที่สุดที่เชื่อมต่อกับจุดยอดใดๆ ในต้นไม้แผ่คลุมขั้นต่ำ (MST) ที่สร้างขึ้นบางส่วน (หรืออนันต์หากไม่มีขอบดังกล่าว) ทุกครั้งที่เลือกจุดยอดvและเพิ่มลงใน MST จะมีการดำเนินการลดค่าคีย์กับจุดยอดw ทั้งหมดที่ อยู่นอก MST บางส่วนซึ่งvเชื่อมต่อกับwโดยตั้งค่าคีย์เป็นค่าต่ำสุดของค่าก่อนหน้าและค่าใช้จ่ายของขอบของ ( v , w )

โดยใช้โครงสร้างข้อมูล ฮีปไบนารีแบบง่ายอัลกอริทึมของ Prim สามารถแสดงให้เห็นว่าทำงานในเวลาO ( | E | log | V | ) โดยที่| E |คือจำนวนขอบและ| V |คือจำนวนจุดยอด การใช้ฮีปฟิโบนาชชี ที่ซับซ้อนกว่า นี้ สามารถลดเวลาการทำงานลงเหลือO ( | E | + | V | log | V | ) ซึ่งเร็วกว่าในเชิง อะซิมโทติก เมื่อกราฟมีความหนาแน่นมากพอที่| E |คือω ( | V | ) และใช้เวลาเชิงเส้นเมื่อ |E| อย่างน้อย |V|  log  |V| สำหรับกราฟที่มีความหนาแน่นมากกว่า (มีขอบอย่างน้อย |V| ^cสำหรับc  >  1 บางค่า) อัลกอริทึมของ Prim สามารถทำให้ทำงานในเวลาเชิงเส้นได้ง่ายยิ่งขึ้น โดยใช้ฮีปd -ary แทนฮีปฟิโบนาชชี^{[ 10 ] [ 11 ]}

ให้Pเป็นกราฟ เชื่อมต่อที่มีน้ำหนัก ในแต่ละรอบของการทำงานของอัลกอริทึมของ Prim จะต้องหาเส้นเชื่อมที่เชื่อมจุดยอดในกราฟย่อยกับจุดยอดนอกกราฟย่อย เนื่องจาก Pเป็นกราฟเชื่อมต่อ จึงจะมีเส้นทางไปยังทุกจุดยอดเสมอ ผลลัพธ์Yของอัลกอริทึมของ Prim คือต้นไม้เพราะเส้นเชื่อมและจุดยอดที่เพิ่มเข้าไปในต้นไม้Yนั้นเชื่อมต่อกัน

ให้Y เป็นต้นไม้แผ่คลุมขั้นต่ำของกราฟ P ถ้าY = Yแล้วYเป็นต้นไม้แผ่คลุมขั้นต่ำ มิฉะนั้น ให้eเป็นขอบแรกที่เพิ่มเข้ามาในระหว่างการสร้างต้นไม้Yที่ไม่ได้อยู่ในต้นไม้Y และVเป็นเซตของจุดยอดที่เชื่อมต่อกันด้วยขอบที่เพิ่มเข้ามาก่อนขอบeดังนั้นจุดปลายด้านหนึ่งของขอบeอยู่ในเซตVและอีกด้านหนึ่งไม่อยู่ เนื่องจากต้นไม้Y เป็นต้นไม้แผ่คลุมของกราฟPจึงมีเส้นทางในต้นไม้Y ที่เชื่อมต่อจุดปลายทั้งสอง เมื่อเดินทางไปตามเส้นทางนั้น จะต้องพบขอบfที่เชื่อมต่อจุดยอดในเซตVกับจุดยอดที่ไม่ได้อยู่ในเซตVในการวนซ้ำเมื่อขอบeถูกเพิ่มเข้าไปในต้นไม้Yขอบfก็อาจถูกเพิ่มเข้าไปด้วย และจะถูกเพิ่มเข้าไปแทนขอบeถ้าค่าน้ำหนักของมันน้อยกว่าeและเนื่องจากขอบfไม่ได้ถูกเพิ่มเข้าไป เราจึงสรุปได้ว่า

${\displaystyle w(f)\geq w(e)}$

ให้ต้นไม้Y2เป็นกราฟที่ได้จากการลบขอบf ออกจาก และเพิ่มขอบeเข้าไปในต้นไม้Y1 สามารถแสดงได้อย่างง่ายดายว่าต้นไม้Y2 เชื่อมต่อ มีจำนวนขอบเท่ากับต้นไม้Y1และน้ำหนักรวมของขอบทั้งหมดไม่เกินน้ำหนักรวมของขอบทั้งหมดของต้นไม้Y1 ดังนั้น ต้นไม้ จึงเป็นต้นไม้แผ่คลุมขั้นต่ำของกราฟPและประกอบด้วยขอบeและขอบทั้งหมดที่เพิ่มเข้ามาก่อนหน้านั้นในระหว่างการสร้างเซตVทำซ้ำขั้นตอนข้างต้นและในที่สุดเราจะได้ต้นไม้แผ่คลุมขั้นต่ำของกราฟPที่เหมือนกับต้นไม้Yซึ่งแสดงให้เห็นว่าYเป็นต้นไม้แผ่คลุมขั้นต่ำ ต้นไม้แผ่คลุมขั้นต่ำช่วยให้เซตย่อยแรกของบริเวณย่อยสามารถขยายออกเป็นเซตย่อยX ที่ใหญ่กว่า ซึ่งเราสมมติว่าเป็นเซตย่อยที่เล็กที่สุด

ลูปหลักของอัลกอริทึมของ Prim นั้นเป็นแบบลำดับโดยเนื้อแท้และไม่สามารถขนานได้อย่างไรก็ตามลูปภายในซึ่งกำหนดขอบถัดไปที่มีน้ำหนักน้อยที่สุดที่ไม่ก่อให้เกิดวงจร สามารถขนานได้โดยการแบ่งจุดยอดและขอบระหว่างโปรเซสเซอร์ที่มีอยู่^{[ 12 ]}รหัสเทียมต่อไปนี้แสดงให้เห็นสิ่งนี้

โดยทั่วไปแล้วอัลกอริธึมนี้สามารถนำไปใช้กับเครื่องกระจาย^{[ 12 ]}เช่นเดียวกับเครื่องหน่วยความจำร่วม^{[ 13 ]}เวลาในการทำงานคือ${\displaystyle O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)}$โดยสมมติว่า การดำเนินการ ลดและกระจายสัญญาณสามารถทำได้ใน${\displaystyle O(\log |P|)}$[ ^{12 ] ได้มีการสำรวจอัลกอริธึมของ Prim เวอร์ชันสำหรับเครื่องหน่วยความ จำ}ร่วม ซึ่งอัลกอริธึมลำดับของ Prim จะทำงานแบบขนาน โดยเริ่มจากจุดยอดที่แตกต่างกัน^{[ 14 ]}อย่างไรก็ตาม ควรสังเกตว่ามีอัลกอริธึมที่ซับซ้อนกว่านี้ในการแก้ ปัญหา ต้นไม้ครอบคลุมขั้นต่ำแบบกระจายได้อย่างมีประสิทธิภาพมากขึ้น

• อัลกอริทึมของไดจ์กสตราเป็นอัลกอริทึมที่คล้ายคลึงกันมากสำหรับปัญหาการหาเส้นทางที่สั้นที่สุด
• กรีดอยด์sนำเสนอวิธีการทั่วไปในการทำความเข้าใจความถูกต้องของอัลกอริทึมของ Prim

• ความคืบหน้าของอัลกอริทึมของ Prim บนจุดที่กระจายแบบสุ่ม
• สื่อที่เกี่ยวข้องกับอัลกอริทึมของ Prim ใน Wikimedia Commons