Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що таке орієнтований граф?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

Орієнтований граф (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
```

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

1. Обходи (DFS/BFS): досяжність, пошук шляхів, перевірка зв'язності за напрямком - O(V+E).
2. Топологічне сортування (для DAG): знаходить лінійний порядок виконання залежностей - O(V+E).
3. Пошук найкоротших шляхів: Dijkstra (без від'ємних ваг), Bellman-Ford (з від'ємними), на DAG - за O(V+E).
4. Сильно зв'язні компоненти: 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, топологічне сортування, найкоротші шляхи) критично важливе для проєктування й оптимізації реальних систем.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати905 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.