נתונה הרשת G = ( V , E ) ומתחילים ליצור עץ פורש מקדקוד כלשהו . /? 5 V בכל שלב נוסיף קשת בעלת משקל מינימלי , המחברת את העץ לקדקוד שלא שייך לעץ . כך גדל העץ הפורש עד שהוא מכיל את כל קדקודי הגרף . G בדומה לאלגוריתם של קרוסקל , גם האלגוריתם של פרים הוא אלגוריתם חמדן , כי בכל צעד הוא מוסיף קשת בעלת משקל קטן ככל האפשר . ניתן להוכיח שאסטרטגיה כזו של בניית עץ פורש מבטיחה שבתום האלגוריתם , E יכיל קשתות המהוות עץ פורש מינימלי . כאמור , מטרתנו למצוא עץ המכיל את כל קדקודי הגרף . לשם פיקוח על כך נשתמש בתור , Q כך ש : V- Q מייצג את קבוצת הקדקודים אשר טופלו ושנמצאים בעץ הפורש , ואילו Q מייצג את קבוצת הקדקודים שעדיין לא טופלו ושאינם נמצאים בעץ הפורש . מאחר שבתחילת האלגוריתם אף קדקוד של הגרף הנתון לא טופל , כל הקדקודים יהיו בתור , ובתום האלגוריתם התור Q יישאר ריק , כיוון שכל הקדקודיס חייבים להיות בעץ הפורש . עבור כל קדקוד , v נשמור בתור Q את , K [ v ] אשר יכיל את המשקל המינימלי מבין משקלי הקשתות המחברות את הקדקוד v לקדקודים השייכים לעץ . כי < - 00 ברור בתחילת האלגוריתם . A V ] ^ בנוסף , עבור כל קדקוד v...
إلى الكتاب