ייצוגי גרפים - מטריצת שכנויות מול רשימת שכנויות

כדי לעבוד עם גרף בקוד, צריך לאחסן אותו בזיכרון. שתי הגישות העיקריות הן מטריצת שכנויות (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))

השוואה