Що таке орієнтований граф?

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

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

Орієнтований граф (directed graph, digraph) - це структура з множини вершин і напрямлених ребер (дуг), де кожне ребро має напрямок: з однієї вершини в іншу, тобто порядок вершин важливий.

Розгорнута відповідь

Визначення та інтуїція

Орієнтований граф G = (V, E) складається з:

V - множина вершин (вузлів);
E - множина орієнтованих ребер (дуг), кожне ребро - впорядкована пара (u, v), що означає зв'язок з u у v.

Головна особливість: наявність напрямку. Ребро (u, v) не еквівалентне (v, u). Це дозволяє моделювати залежність, порядок і потік: звідки й куди «тече» зв'язок або дані.

Ключові поняття

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

Де застосовується в розробці

Граф залежностей модулів/пакетів, порядок збирання (topological sort у CI/CD).
Граф маршрутів, навігації та переадресацій.
Робочі процеси/пайплайни (завдання, що потребують попередніх кроків).
Мікросервіси та взаємодії: виклики A → B, потоки подій.
Графи станів (finite state machines) з переходами.

Простий приклад

Вершини: A, B, C, D
Дуги: A→B, A→C, B→D, C→D

Діаграма:
A → B → D
  ↘ C ↗

Представлення в пам'яті

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

Представлення	Характеристики
Список суміжності	Пам'ять ~ O(V+E), швидкий обхід сусідів, перевірка ребра за O(min(deg, ...))
Матриця суміжності	Пам'ять ~ O(V^2), миттєва перевірка ребра за O(1), зручна для щільних графів

Список суміжності (приклад на JS)

// Граф з прикладу: A→B, A→C, B→D, C→D
const adj = {
  A: ["B", "C"],
  B: ["D"],
  C: ["D"],
  D: []
};

// Напівстепені заходу (in-degree) та виходу (out-degree)
const outDegree = Object.fromEntries(Object.keys(adj).map(v => [v, adj[v].length]));
const inDegree = Object.fromEntries(Object.keys(adj).map(v => [v, 0]));
for (const u of Object.keys(adj)) for (const v of adj[u]) inDegree[v]++;

console.log({ inDegree, outDegree });

Матриця суміжності (для тих самих вершин A,B,C,D)

const V = ["A","B","C","D"];
//    A B C D
// A: 0 1 1 0
// B: 0 0 0 1
// C: 0 0 0 1
// D: 0 0 0 0
const matrix = [
  [0,1,1,0],
  [0,0,0,1],
  [0,0,0,1],
  [0,0,0,0]
];

function hasEdge(u, v) {
  const i = V.indexOf(u), j = V.indexOf(v);
  return matrix[i][j] === 1;
}

console.log(hasEdge("A", "C")); // true

Базові алгоритми для орієнтованих графів

Обходи (DFS/BFS): досяжність, пошук шляхів, перевірка зв'язності за напрямком - O(V+E).
Топологічне сортування (для DAG): знаходить лінійний порядок виконання залежностей - O(V+E).
Пошук найкоротших шляхів: Dijkstra (без від'ємних ваг), Bellman-Ford (з від'ємними), на DAG - за O(V+E).
Сильно зв'язні компоненти: Kosaraju/Tarjan - групують вершини, взаємно досяжні за напрямками.

Реалізація топологічного сортування (Kahn) + детекція циклу

function topoSort(adj) {
  // Рахуємо in-degree
  const inDeg = Object.fromEntries(Object.keys(adj).map(v => [v, 0]));
  for (const u in adj) for (const v of adj[u]) inDeg[v] = (inDeg[v] ?? 0) + 1;

  // Черга вершин без вхідних ребер
  const q = [];
  for (const v in inDeg) if (inDeg[v] === 0) q.push(v);

  const order = [];
  while (q.length) {
    const u = q.shift();
    order.push(u);
    for (const v of adj[u]) {
      inDeg[v]--;
      if (inDeg[v] === 0) q.push(v);
    }
  }

  // Якщо в порядку менше вершин, ніж у графі - є цикл
  const hasCycle = order.length !== Object.keys(adj).length;
  return { order: hasCycle ? null : order, hasCycle };
}

const adj1 = { A:["B","C"], B:["D"], C:["D"], D:[] };
console.log(topoSort(adj1)); // { order: [ 'A', 'B', 'C', 'D' ] (або 'A','C','B','D'), hasCycle: false }

const adj2 = { A:["B"], B:["C"], C:["A"] }; // цикл A→B→C→A
console.log(topoSort(adj2)); // { order: null, hasCycle: true }

DFS з детекцією циклу в орієнтованому графі

function hasDirectedCycle(adj) {
  const Color = { WHITE:0, GRAY:1, BLACK:2 };
  const color = Object.fromEntries(Object.keys(adj).map(v => [v, Color.WHITE]));
  let cycle = false;

  function dfs(u) {
    color[u] = Color.GRAY;
    for (const v of adj[u]) {
      if (color[v] === Color.GRAY) cycle = true;          // зворотне ребро: цикл
      else if (color[v] === Color.WHITE) dfs(v);
    }
    color[u] = Color.BLACK;
  }

  for (const v in adj) if (color[v] === Color.WHITE) dfs(v);
  return cycle;
}

console.log(hasDirectedCycle({ A:["B"], B:["C"], C:["A"] })); // true
console.log(hasDirectedCycle({ A:["B","C"], B:["D"], C:["D"], D:[] })); // false

Складність

Пам'ять: список суміжності - O(V+E), матриця - O(V^2).
DFS/BFS/топологічне сортування - O(V+E).
Пошук SCC (Tarjan/Kosaraju) - O(V+E).

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

Плутати орієнтовані та неорієнтовані ребра: у digraph напрямок критично важливий.
Ігнорувати цикли в графі залежностей: топологічне сортування неможливе за наявності циклів.
Неправильно рахувати степені: in-degree та out-degree - різні величини.
Обирати неефективне представлення: матриця суміжності для розрідженого графа призводить до зайвих витрат пам'яті.

Орієнтований граф - базова структура для моделювання напрямлених залежностей і процесів. Знання представлень (список/матриця), властивостей (in/out-degree, цикли, SCC) і базових алгоритмів (DFS/BFS, топологічне сортування, найкоротші шляхи) критично важливе для проєктування й оптимізації реальних систем.

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

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

Premium

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