|
|
עמוד:345
6 . 4 . 1 הצגת האלגוריתם של פרים אלגוריתם Prim ( G , r ) האלגוריתם מקבל כקלט את הגרף הבלתי מכוון והקשיר G ואת השורש r של העץ הפורש המינימלי שהאלגוריתם צריך לבנות . צעד 1 לכל קדקוד v בצע : K [ v ] < - 00 1 . 1 nrf ? r TIN v ) on 1 . 2 . < 2 סוף הלולאה . צעד 2 ATr ]< -0 2 . 1 < - nil 2 . 2 [ />[/ צעד 3 כל עוד התור Q לא ריק ( כלומר לא כל הקדקודים נמצאים עדיין בעץ הפורש , IT בצע י 3 . 1 הוצא את הקדקוד u מהתור , Q כך שלכל קדקוד v eQ K [ u ] = min { A' [ v ]} ( כלומר מוציאים מהתור Q את הקדקוד » המקיים K [ v ] > K [ u ] לכל קדקוד v בתור . ( 3 . 2 עבור כל קדקוד , v שהנו שכן של הקדקוד u ושעדיין נמצא בתור , Q בדוק : אם w ( u , v ) < K [ v ] ( כלומר הקשת ( u , v ) היא בעלת המשקל המינימלי מבין משקלי הקשתות המחברות את הקדקוד v לקדקודים שבחרנו עד כה ) אז בצע *) P [ v ] < - u 3 . 2 . 1 נקבע הורה חדש (* *) K [ v ] < - w ( u , v ) 3 . 2 . 2 נקבע משקל חדש (* סוף הלולאה . בכל שלב של האלגוריתם קיים תור של קדקודי הגרף שממנו מוציאים קדקוד אחד , « בעל הערך K [ u ] הקטן ביותר . לאחר מכן מעדכנים ( אם צריך ) את הערך של K [ v ] עבור כל קדקוד
|
|