ייצוגי גרפים - מטריצת שכנויות מול רשימת שכנויות
השוואה בין שתי הדרכים העיקריות לייצג גרף בקוד, וההשפעה על ביצועי האלגוריתמים.
כדי לעבוד עם גרף בקוד, צריך לאחסן אותו בזיכרון. שתי הגישות העיקריות הן מטריצת שכנויות (Adjacency Matrix) ורשימת שכנויות (Adjacency List), ולכל אחת יתרונות וחסרונות.
מטריצת שכנויות
מטריצה בגודל V×V שבה matrix[i][j] = 1 אם יש קשת מ-i ל-j (או המשקל שלה בגרף משוקלל), אחרת 0.
// Graph with 4 nodes, edges: 0-1, 0-2, 1-3
const matrix = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 0],
[0, 1, 0, 0],
];
// Check edge: matrix[0][2] === 1 -> O(1)רשימת שכנויות
מערך שבו לכל צומת יש רשימה של שכניו. זה הייצוג הנפוץ יותר בפועל, במיוחד לגרפים דלילים.
const adj = {
0: [1, 2],
1: [0, 3],
2: [0],
3: [1],
};
// Iterate neighbors of 0: O(deg(0))השוואה
| קריטריון | מטריצת שכנויות | רשימת שכנויות |
|---|---|---|
| זיכרון | O(V²) | O(V + E) |
| בדיקה אם יש קשת (u,v) | O(1) | O(deg(u)) |
| מעבר על שכנים של u | O(V) | O(deg(u)) |
| הוספת קשת | O(1) | O(1) |
| מתאים ל- | גרפים צפופים | גרפים דלילים |
ברוב היישומים בעולם האמיתי (רשתות חברתיות, מפות, אינטרנט) הגרפים דלילים - E ≪ V². לכן רשימת שכנויות היא ברירת המחדל בפועל ובאלגוריתמים כמו BFS, DFS ו-Dijkstra.
שאלות נפוצות
מה ההבדל בין מטריצת שכנויות לרשימת שכנויות?
מטריצת שכנויות היא מערך דו-ממדי בגודל V×V שבו כל תא מציין אם קיימת קשת בין שני צמתים. רשימת שכנויות מחזיקה לכל צומת רשימה של שכניו בלבד. המטריצה צורכת O(V²) זיכרון תמיד, בעוד הרשימה צורכת O(V+E) — הבדל עצום בגרפים דלילים.
מתי עדיף להשתמש במטריצת שכנויות?
כשהגרף צפוף, כלומר מספר הקשתות מתקרב ל-V², וכשצריך לבדוק תכופות אם קיימת קשת בין שני צמתים ספציפיים — בדיקה זו היא O(1) במטריצה לעומת O(degree) ברשימה. מטריצה גם נוחה לאלגוריתמים המבוססים על כפל מטריצות, כמו פלויד-וורשל למסלולים קצרים בין כל הזוגות.
איזה ייצוג מתאים לרוב האלגוריתמים?
רשימת שכנויות, ברוב המקרים המעשיים. גרפים בעולם האמיתי דלילים בדרך כלל, ואלגוריתמים כמו חיפוש לרוחב, חיפוש לעומק ודייקסטרה סורקים את שכני כל צומת — פעולה שרשימת שכנויות מבצעת ביעילות. עם מטריצה, סריקת השכנים עולה O(V) לכל צומת והסיבוכיות הכוללת מתדרדרת ל-O(V²).