|
|
עמוד:173
אם , G [/][/] = i אזי ניתן לומר שקיימת קשת מקדקוד שמספרו , / לקדקוד שמספרו j ואס ערכו , 0 אזי לא קיימת הקשת . מאחר שהחלטנו לממש את הגרף ( באפשרות הראשונה ) על-ידי שימוש במערך דו-ממדי ( מטריצה ריבועית , ( נציג כעת את השגרות / פונקציות למימוש הפעולות הבסיסיות שהזכרנו קודם במפרט . מימוש אלגוריתמי של פעולות הממשק כאשר הגרף מיוצג כמטריצת סמיכויות : אתחל-גרף (») } פעולה המחזירה גרף בעל n צמתים ריק מקשתות . « > 0 G משתנה מהטיפוס גרף . >•<« { . 0 < x , ( 1 ) עבור * 0-מ עד >! -1 בצע : ( 1 . 1 ) > 'עבור 0-מ עד 7 ! -1 בצע : [ x , y ] ^ O ( 1 . 1 . 1 ) ( 2 ) החזר ס הוסף-קשת ( ע :, ג ( 0 , | פעולה המוסיפה קשת מצומת . v לצומת f בגרף G הגרף G מאותחל . . 0 < x , y < n אין קשת מצומת x לצומת ץ . { ( 1 ) G [ x , v ] < - 1 הוסף-קשת-משוקללת ( G , x , y , >?>) } פעולה המוסיפה קשת , שמשקלה , w מצומת x לצומת y בגרף G הגרף G מאותחל . . 0 < x , y < n אין קשת מצומת x לצומת ( . v ( 2 ) G [; t , y ] < - w ניתן לאחסן בתא [/ , /] של המטריצה את המשקל של הקשת , (/ ,, /) בתנאי שהמשקל של כל קשת שונה מאפס .
|
|