|
|
עמוד:346
שנשאר בתור . לכן יש צורך לייצג את התור באמצעות מבנה נתונים שעליו מוגדרות הפעולות הבסיסיות שלהלן : - EXTRACT _ MIN ( 2 ) מוציאה מהתור Q את האיבר u בעל הערך ( K [ u ]) הקטן ביותר מבין כל האיברים שבתור Q ומחזירה אותו . - DECREASE _ KEY (( 2 , v , k [ v ] ) מעדכנת את הערך של . K [ v ] לאור האמור לעיל , להלן האלגוריתם של פרים תוך שימוש בפעולות הבסיסיות המוגדרות על מבנה הנתונים תור : PRIM ( G , r ) // INIT step 1 : for each vertex v do K [ v ] < - x P [ v ] < - NULL step 2 : K [ r ] < - 0 P [ r ] < - NULL PQ <— V // Priority Queue holds the vertices outside the tree // // GROW TREE step 3 : while Pg *< j ) do ( 3 . 1 ) w < - EXTRACT _ MIN ( P 2 ) ( 3 . 2 ) for each v e adj [ w ] do ( 3 . 2 . 1 ) ifve P 0 and w ( u , v ) < K [ v ] then ( 3 . 2 . 1 . 1 ) A ^ v ] < - W ( M , V ) ( 3 . 2 . 1 . 2 ) P [ v ] < - « ( 3 . 2 . 1 . 3 ) DECREASE _ KEY ( Pg , v , KM ) נדגים את אופן הפעולה של האלגוריתם של פרים על הרשת שלהלן י adj [«] מציין קבוצת קדקודים שהם שכנים של הקדקוד . u
|
|