Як можна зберігати граф у пам'яті?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Граф у пам'яті зазвичай зберігають як: 1) матрицю суміжності (O(V^2), швидкі перевірки ребра), 2) список суміжності (O(V+E), швидка ітерація по сусідах, зручне додавання/видалення), 3) список ребер (O(E), просте завантаження і зберігання), 4) стиснуті структури CSR/CSC для великих розріджених графів. Вибір залежить від щільності графа, потрібних операцій (перевірка ребра, обхід сусідів, оновлення) та обмежень за пам'яттю.

Детальна відповідь

Основні способи зберігання

Матриця суміжності: двовимірний масив V×V. Пам'ять O(V^2). Перевірка наявності ребра O(1). Ітерація по сусідах O(V). Добра для щільних графів і частих перевірок ребра.
Список суміжності: для кожної вершини список/множина сусідів. Пам'ять O(V+E). Перевірка ребра O(deg(u)) або O(1) з Set. Ітерація по сусідах O(deg(u)). Найкращий вибір для розріджених і динамічних графів.
Список ребер: масив пар/трійок (u, v, w). Пам'ять O(E). Зручний для зберігання, серіалізації та алгоритмів на ребрах. Перевірка ребра O(E) (якщо не індексувати).
CSR/CSC: стиснуті формати для розріджених графів. Пам'ять близька до O(V+E). Відмінна ітерація по сусідах і cache-friendly обходи. Складно/дорого оновлювати онлайн.

Матриця суміжності (Adjacency Matrix)

Двовимірний масив розміром V×V, де елемент matrix[u][v] = 0/1 або вага ребра. Для неорієнтованого графа матриця симетрична.

Пам'ять: O(V^2). Для великих розріджених графів - неефективно.
Перевірка ребра u→v: O(1). Ітерація сусідів: O(V).
Додавання вершини: O(V^2) (перевиділення). Додавання ребра: O(1).
Підходить для щільних графів і задач з частими перевірками наявності ребра.

const n = 5; // кількість вершин
const matrix = Array.from({ length: n }, () => Array(n).fill(0));

function addEdge(u, v, w = 1, directed = false) {
  matrix[u][v] = w; // 1 або вага
  if (!directed) matrix[v][u] = w;
}

function hasEdge(u, v) {
  return matrix[u][v] !== 0;
}

function neighbors(u) {
  const res = [];
  for (let v = 0; v < n; v++) if (matrix[u][v] !== 0) res.push(v);
  return res;
}

addEdge(0, 1);
addEdge(0, 3);
console.log(hasEdge(0, 1)); // true
console.log(neighbors(0));  // [1, 3]

Список суміжності (Adjacency List)

Для кожної вершини зберігаємо колекцію її сусідів: масив, Set або Map (для зважених графів). Добре масштабується для розріджених графів і підтримує динамічні зміни.

Пам'ять: O(V+E).
Перевірка ребра: O(deg(u)) з масивом, O(1) з Set/Map.
Ітерація сусідів: O(deg(u)). Додавання/видалення ребра: амортизовано O(1).

// Незважений граф: Map<number, Set<number>>
const g = new Map();

function addVertex(u) {
  if (!g.has(u)) g.set(u, new Set());
}

function addEdge(u, v, directed = false) {
  addVertex(u); addVertex(v);
  g.get(u).add(v);
  if (!directed) g.get(v).add(u);
}

function hasEdge(u, v) {
  return g.has(u) && g.get(u).has(v);
}

function neighbors(u) {
  return g.get(u) ? [...g.get(u)] : [];
}

function removeEdge(u, v, directed = false) {
  if (g.has(u)) g.get(u).delete(v);
  if (!directed && g.has(v)) g.get(v).delete(u);
}

// Приклад використання
addEdge(0, 1);
addEdge(0, 2);
console.log(hasEdge(0, 1)); // true
console.log(neighbors(0));  // [1, 2]

// Зважений граф: Map<number, Map<number, number>>
const wg = new Map();

function addWeightedEdge(u, v, w, directed = false) {
  if (!wg.has(u)) wg.set(u, new Map());
  if (!wg.has(v)) wg.set(v, new Map());
  wg.get(u).set(v, w);
  if (!directed) wg.get(v).set(u, w);
}

function weight(u, v) {
  return wg.has(u) ? wg.get(u).get(v) : undefined; // undefined = ребра немає
}

addWeightedEdge(1, 3, 2.5);
console.log(weight(1, 3)); // 2.5

Список ребер (Edge List)

Зберігаємо масив ребер, кожне ребро - пара (u, v) або трійка (u, v, w). Простий формат для обміну даними та деяких алгоритмів (наприклад, сортування за вагою для Крускала).

Пам'ять: O(E).
Перевірка ребра: O(E), якщо не будувати індекси.
Ітерація по сусідах вимагає індексації/групування.

// Список ребер: [[u, v, w?]]
const edges = [ [0, 1], [0, 2], [2, 3] ];

// Для швидкого доступу до сусідів - згрупуємо в список суміжності під час завантаження
const adj = new Map();
for (const [u, v] of edges) {
  if (!adj.has(u)) adj.set(u, []);
  adj.get(u).push(v);
}
console.log(adj.get(0)); // [1, 2]

CSR/CSC (Compressed Sparse Row/Column)

Стиснуті структури для розріджених графів (за аналогією зі розрідженими матрицями). CSR зберігає всіх сусідів вершини поспіль в одному масиві та масив зміщень для швидкого доступу.

Пам'ять: близько до O(V+E), добра локальність у пам'яті.
Ідеально для обходів і обчислень на великих графах. Оновлення (додавання/видалення) незручні - потрібна перебудова.

// Побудова CSR зі списку ребер
function buildCSR(n, edges, directed = false) {
  const tmp = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    tmp[u].push(v);
    if (!directed) tmp[v].push(u);
  }
  const offsets = new Uint32Array(n + 1);
  let total = 0;
  for (let i = 0; i < n; i++) {
    offsets[i] = total;
    total += tmp[i].length;
  }
  offsets[n] = total;
  const neighbors = new Uint32Array(total);
  let idx = 0;
  for (let i = 0; i < n; i++) {
    for (const v of tmp[i]) neighbors[idx++] = v;
  }
  return { offsets, neighbors };
}

function neighborsCSR(csr, u) {
  const { offsets, neighbors } = csr;
  return neighbors.subarray(offsets[u], offsets[u + 1]);
}

const csr = buildCSR(5, [[0,1],[0,2],[2,3]]);
console.log([...neighborsCSR(csr, 0)]); // [1, 2]

Матриця інцидентності та інші варіанти

Матриця інцидентності: V×E, корисна для деяких теоретичних/лінійно-алгебраїчних задач. Пам'ять O(V·E) - рідко використовується на практиці для великих графів.
Об'єктна модель (вузли/ребра як об'єкти з посиланнями): зручно для складних атрибутів, але дорожче за пам'яттю і кешем.

Порівняння за операціями (усереднено)

Пам'ять: матриця O(V^2) > список суміжності O(V+E) ≈ CSR O(V+E) > список ребер O(E) (без індексів).
Перевірка ребра u→v: матриця O(1), список суміжності O(deg(u)) або O(1) при Set/Map, CSR O(log deg(u)) при бінарному пошуку (якщо відсортовано) або O(deg(u)).
Ітерація сусідів: список суміжності/CSR O(deg(u)) - швидше і кеш-дружелюбніше, матриця O(V).
Оновлення: список суміжності - дешеві; матриця - дешево для ребер, дорого для вершин; CSR - дорого (перебудова).

Як обрати структуру

Щільний граф (багато ребер) і важлива перевірка наявності ребра: матриця суміжності.
Розріджений граф, часті обходи й оновлення: список суміжності (Set/Map).
Дуже великий розріджений граф, мало/жодних оновлень, важлива продуктивність обходу: CSR/CSC.
Просте зберігання/обмін: список ребер.

Особливості: напрямлені, зважені, мультиграфи

Напрямлені: зберігайте лише u→v (не дублюйте v→u). У матриці - несиметричні елементи.
Зважені: у матриці - числа ваг, у списку суміжності - Map<сусід, вага> або масив об'єктів { to, w }.
Мультиграфи: дозволені кратні ребра. У списку суміжності використовуйте масив (не Set) або зберігайте лічильник/список ребер між парою вершин.
Петлі (u=u): підтримуються всіма структурами; у матриці - діагональні елементи.

Приклад: типовий граф для веб-задач (обходи BFS/DFS)

// Список суміжності з Set: зручно і швидко для перевірок
const G = new Map();
const dir = false; // неорієнтований

function v(u){ if(!G.has(u)) G.set(u, new Set()); }
function add(u,v){ v(u); v(v); G.get(u).add(v); if(!dir) G.get(v).add(u); }

// Побудуємо невеликий граф
add(0,1); add(0,2); add(1,3); add(2,3); add(3,4);

function bfs(start){
  const q = [start], seen = new Set([start]), order = [];
  while(q.length){
    const u = q.shift(); order.push(u);
    for(const v of G.get(u) || []) if(!seen.has(v)){ seen.add(v); q.push(v); }
  }
  return order;
}

function dfs(start){
  const st = [start], seen = new Set(), order = [];
  while(st.length){
    const u = st.pop();
    if(seen.has(u)) continue; seen.add(u); order.push(u);
    for(const v of G.get(u) || []) if(!seen.has(v)) st.push(v);
  }
  return order;
}

console.log('BFS:', bfs(0)); // наприклад, [0,1,2,3,4]
console.log('DFS:', dfs(0));

Підсумки

Немає єдино правильного представлення: обирайте під задачі та обмеження.
Матриця - для щільних графів і частих перевірок ребра; список суміжності - універсальний і динамічний вибір; список ребер - простий формат даних; CSR/CSC - для великих розріджених графів і високопродуктивних обходів.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.