З чого складається граф?

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

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

Граф - це абстрактна структура, яка складається з:

множини вершин V (вузлів);
множини ребер E, де кожне ребро з'єднує одну або дві вершини.

Ребра можуть бути орієнтованими або неорієнтованими, зваженими або незваженими; допускаються петлі та паралельні ребра (у мультиграфах).

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

Основні елементи графа

Вершини (V, вузли): об'єкти/сутності. Можуть мати ідентифікатор, мітку та атрибути (наприклад, ім'я, координати, властивості).
Ребра (E): зв'язки між вершинами. У неорієнтованому графі ребро - невпорядкована пара {u, v}, в орієнтованому - впорядкована пара (u → v). Ребра можуть зберігати ваги/вартості та інші атрибути.

Властивості ребер і варіанти графів

Орієнтованість: орієнтовані (дуги) vs неорієнтовані. В орієнтованому графі розрізняють напівстепінь виходу (out-degree) і напівстепінь заходу (in-degree).
Зваженість: ребро може мати вагу (вартість, відстань, пропускну здатність). У незваженому графі всі ваги рівні, зазвичай 1.
Кратність: простий граф (немає петель і паралельних ребер) vs мультиграф (дозволені паралельні ребра).
Петлі: ребро, що з'єднує вершину саму із собою (u → u).
Мітки/атрибути: як у вершин, так і у ребер (наприклад, тип зв'язку, часові мітки).

Базові поняття

Суміжність та інцидентність: вершини u і v суміжні, якщо між ними є ребро; ребро інцидентне своїм вершинам.
Степінь вершини: кількість інцидентних ребер. Для орієнтованого графа: in-degree та out-degree.
Шлях/маршрут і довжина шляху: послідовність вершин, з'єднаних ребрами; довжина - кількість ребер або сума ваг.
Цикл та ациклічність: цикл починається і закінчується в одній вершині; відсутність циклів - ациклічний граф (наприклад, DAG).
Компоненти зв'язності: максимальні підмножини вершин, між якими є шляхи.
Особливі види: дерево (зв'язний ациклічний), ліс (набір дерев), повний граф, двочастковий граф.

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

Список суміжності (Adjacency List): ефективний за пам'яттю для розріджених графів; швидкий обхід сусідів.

// JS: орієнтований зважений граф (список суміжності) const graph = { A: [{ to: 'B', w: 5 }, { to: 'D', w: 1 }], B: [{ to: 'C', w: 2 }], C: [], D: [{ to: 'C', w: 3 }] }; // обхід сусідів A for (const edge of graph.A) { console.log(`A -> ${edge.to} (w=${edge.w})`); }
Матриця суміжності (Adjacency Matrix): швидка перевірка наявності ребра O(1), зручна для щільних графів; потребує O(n²) пам'яті.

// Матриця суміжності для вершин [A,B,C,D] // 0 - немає ребра, інакше вага const V = ['A','B','C','D']; const M = [ /*A*/ [0, 5, 0, 1], /*B*/ [0, 0, 2, 0], /*C*/ [0, 0, 0, 0], /*D*/ [0, 0, 3, 0] ]; // Перевірка ребра A->B const i = V.indexOf('A'); const j = V.indexOf('B'); console.log(M[i][j] !== 0); // true
Список ребер (Edge List): просте зберігання набору ребер; зручно для алгоритмів, яким потрібен повний перелік ребер (наприклад, Крускал).

// Список ребер (u, v, w) const edges = [ ['A','B',5], ['A','D',1], ['B','C',2], ['D','C',3] ];

Міні-приклад: орієнтований зважений граф

Нехай V = {A, B, C, D}, E = {(A→B, 5), (A→D, 1), (B→C, 2), (D→C, 3)}.

Out-degree: deg⁺(A)=2, deg⁺(B)=1, deg⁺(C)=0, deg⁺(D)=1.
In-degree: deg⁻(A)=0, deg⁻(B)=1, deg⁻(C)=2, deg⁻(D)=1.
Найкоротший шлях за вагами A → C: A→D→C (вага 1+3=4) коротший, ніж A→B→C (5+2=7).

// Простий Дейкстра для додатних ваг (JS)
function dijkstra(adj, src) {
  const dist = Object.fromEntries(Object.keys(adj).map(v => [v, Infinity]));
  dist[src] = 0;
  const visited = new Set();

  while (visited.size < Object.keys(adj).length) {
    let u = null, best = Infinity;
    for (const v of Object.keys(adj)) {
      if (!visited.has(v) && dist[v] < best) { best = dist[v]; u = v; }
    }
    if (u === null) break;
    visited.add(u);
    for (const { to, w } of adj[u]) {
      if (dist[u] + w < dist[to]) dist[to] = dist[u] + w;
    }
  }
  return dist;
}

const adj = {
  A: [{ to: 'B', w: 5 }, { to: 'D', w: 1 }],
  B: [{ to: 'C', w: 2 }],
  C: [],
  D: [{ to: 'C', w: 3 }]
};

console.log(dijkstra(adj, 'A')); // { A:0, B:5, C:4, D:1 }

Як коротко відповісти на співбесіді (30-60 секунд)

Граф - це пара множин (V, E): вершини та ребра.
Ребра бувають орієнтованими/неорієнтованими, можуть мати вагу; можливі петлі та паралельні ребра.
Ключові поняття: степінь, шлях, цикл, компоненти зв'язності.
Зберігання: список суміжності, матриця суміжності, список ребер (залежно від щільності та задач).

Часті помилки

Підміняти визначення графа його реалізацією (наприклад, «це об'єкт з масивами сусідів»).
Забувати згадати спрямованість/ваги/петлі та мультиграфи.
Плутати степінь вершини з кількістю сусідів в орієнтованих графах (потрібно розрізняти in та out).
Обирати неефективне представлення (наприклад, матрицю для дуже розрідженого графа).

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

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

Premium

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