Алгоритми на графах та їх складність (пошук вшир/вглиб, компоненти, кістякове дерево, найкоротші шляхи)

📌 Про що ця тема

Тут перевіряють, чи вмієш ти працювати з графами: правильно обходити вершини, знаходити компоненти звʼязності, будувати кістякове дерево і шукати найкоротші шляхи. Ключове поняття — граф (множина вершин і ребер) та алгоритми, що його опрацьовують, разом з оцінкою їхньої складності O(…).

📖 Головне

• Граф G = (V, E): V — вершини, E — ребра. Ребра бувають орієнтовані (напрямлені) і неорієнтовані; графи — зважені (на ребрах є числа-ваги) і незважені.

• Способи зберігання: матриця суміжності (таблиця V×V, памʼять O(V²), перевірка ребра за O(1)) та список суміжності (для кожної вершини — список сусідів, памʼять O(V+E), економніша для розріджених графів).

• Пошук вшир (BFS): обходить граф «шарами» від старту, використовує чергу. Знаходить найкоротший шлях у НЕзваженому графі (за кількістю ребер). Складність O(V+E) зі списком суміжності.

• Пошук вглиб (DFS): іде якомога далі по одній гілці, потім вертається (рекурсія або стек). Застосування: пошук циклів, топологічне сортування, компоненти. Складність O(V+E).

• Компоненти звʼязності: максимальні підмножини вершин, де між будь-якими двома є шлях. Щоб їх порахувати — запускаєш BFS/DFS з кожної ще не відвіданої вершини; кількість запусків = кількість компонент.

• Кістякове (остовне) дерево: підграф, що зʼєднує всі вершини без циклів; має рівно V−1 ребро. Мінімальне кістякове дерево (MST) — з найменшою сумою ваг.

• Алгоритм Прима: нарощує дерево, щоразу додаючи найдешевше ребро до нової вершини. Алгоритм Крускала: сортує всі ребра за вагою і додає ребро, якщо воно не утворює цикл.

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

🔢 Як це працює на прикладі

Граф: вершини A,B,C,D; ребра A–B, A–C, B–D. Запускаємо BFS від A.

• Крок 1: черга [A], відстань A=0.

• Крок 2: беремо A, додаємо сусідів B і C → відстань 1, черга [B,C].

• Крок 3: беремо B, його новий сусід D → відстань 2, черга [C,D].

• Крок 4: беремо C (нових немає), потім D (нових немає).

Результат: найкоротші відстані A→B=1, A→C=1, A→D=2. Усі вершини досяжні → граф має 1 компоненту звʼязності.

⚠️ Типові помилки

• Плутають BFS і DFS: BFS дає найкоротший шлях у незваженому графі, а DFS — ні.

• Застосовують BFS для пошуку найкоротшого шляху у ЗВАЖЕНОМУ графі — там потрібен Дейкстра.

• Забувають позначати вершину відвіданою → нескінченний цикл або повторні обходи.

• Думають, що кістякове дерево має V ребер — насправді V−1.

• Плутають матрицю суміжності (O(V²)) зі списком (O(V+E)) при оцінці памʼяті.

🎯 Що завчити напамʼять

• BFS і DFS: складність O(V+E).

• BFS — черга, DFS — стек/рекурсія.

• Кістякове дерево: V−1 ребро, без циклів.

• MST: Прим і Крускал.

• Дейкстра — найкоротші шляхи за невідʼємних ваг.

• Матриця суміжності — O(V²), список — O(V+E).

🧠 Перевір себе

1. Який алгоритм гарантує найкоротший шлях у незваженому графі?

2. Скільки ребер у кістяковому дереві графа з 10 вершин?

3. Яку структуру даних використовує BFS?

4. Чим Дейкстра відрізняється від BFS?

Відповіді: 1 — пошук вшир (BFS); 2 — дев'ять (V−1); 3 — чергу; 4 — Дейкстра враховує ваги ребер і працює для зважених графів з невідʼємними вагами, BFS — лише для незважених (рахує кількість ребер).