|
|
עמוד:171
שאלה 4 . 13 לאור האמור לעיל , מהו מבנה הנתונים שנשתמש בו להצגת גרף ? נכנה את המערך הדו-ממדי מסדר . G-D n x n מערך דו-ממדי ( מטריצה ריבועית ) מייצג כל זוג אפשרי של צמתים שניתן להעביר ביניהם קשת . דוגמה , נתון הגרף המכוון הזה : כדי לייצג אותו נשתמש במטריצה הריבועית שלהלן ו השותת הן צמתים מהם יוצאות הקשתות , והעמודות הן הצמתים אליהם הקשתות נכנסות . במטריצה זו נרשום 1 ( או הערך ( TRUE או 0 ( או הערך DN . ( FALSE הקדקוד j סמוך לקדקוד / ( קיימת קשת , ( אזי ערכו של G [ i ][ f ] יהיה ( TRUE ) 1 ואם הקדקוד j אינו סמוך לקדקוד / ( כלומר לא קיימת קשת , ( אזי ערכו של G [ i ]\ j ] יהיה . ( FALSE ) 0 בדוגמה שלנו G [ O ][ 1 ] r 1 מאחר שקיימת קשת מקדקוד 0 לקדקוד . 1 כמו כן , G [ l ][ 0 ] = 0 מאחר שלא קיימת קשת מקדקוד 1 לקדקוד . 0 הערה : עבור הגרף הלא מכוון , G המערך הדו-ממדי יוגדר כדלהלן ? אס קיימת קשת לא מכוונתי , 1 f (/ אם 1 0 0 ? I ' =. / אחרת 0 לדוגמה , בהינתן הגרף הזה :
|
|