Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке Breadth-First Search (пошук у ширину)?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Breadth-First Search (BFS, пошук у ширину)** - це алгоритм обходу графа/дерева, який відвідує вершини «по шарах» від стартової вершини, використовуючи чергу. Він гарантує знаходження найкоротшого шляху за кількістю ребер у неважених графах і працює за O(V+E) за часом і O(V) за пам'яттю. **Ключове:** позначайте visited під час додавання в чергу, а не під час вилучення - інакше вершини можуть потрапити в чергу кілька разів.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Breadth-First Search (BFS, пошук у ширину) - це алгоритм обходу графа/дерева, який відвідує вершини «по шарах» від стартової вершини, використовуючи чергу. Він гарантує знаходження найкоротшого шляху за кількістю ребер у неважених графах і працює за O(V+E) за часом і O(V) за пам'яттю. ## Розгорнута відповідь ### Визначення BFS - це алгоритм, який починає обхід із заданої стартової вершини і послідовно відвідує всі вершини на відстані 1 ребро, потім відстані 2 ребра і так далі. Для керування порядком відвідування використовується черга (FIFO). Такий «шаровий» обхід дозволяє коректно вимірювати мінімальну кількість ребер від джерела до кожної досяжної вершини в неваженому графі. ### Ключова ідея - Помістити стартову вершину в чергу, позначити її як відвідану, встановити відстань до неї рівною 0. - Поки черга не порожня: витягти вершину u з початку черги, «розширити» її - пройти по всіх сусідах v. - Якщо сусід v ще не відвіданий: позначити відвідування при додаванні в чергу, записати батька v = u, відстань dist[v] = dist[u] + 1, покласти v у кінець черги. ### Властивості і гарантії - Шаровість: вершини відвідуються в порядку незростання найкоротшої відстані від джерела. - Найкоротші шляхи в неважених графах: BFS знаходить мінімальну кількість ребер від джерела до кожної досяжної вершини. - Працює і для орієнтованих, і для неорієнтованих графів (з урахуванням напрямку ребер). - Підходить для дерев (дає обхід по рівнях, level-order traversal). ### Складність - Час: O(V + E), де V - кількість вершин, E - кількість ребер. - Пам'ять: O(V) для черги, масивів dist/visited/parent. ### Структури даних - Черга (FIFO) - керує порядком обходу рівнів. - visited - позначає, що вершину вже поставлено в чергу (важливо позначати при додаванні, а не при вилученні). - dist - відстань у ребрах від джерела до вершини. - parent - батько вершини в дереві BFS для відновлення шляху. ### Псевдокод (JavaScript) ``` function bfs(adj, start) { const n = adj.length; const dist = Array(n).fill(Infinity); const parent = Array(n).fill(-1); const visited = Array(n).fill(false); const q = []; let head = 0; // реалізація черги через масив і покажчик голови q.push(start); visited[start] = true; dist[start] = 0; while (head < q.length) { const u = q[head++]; for (const v of adj[u]) { if (!visited[v]) { visited[v] = true; // позначаємо при додаванні parent[v] = u; // запам'ятовуємо дерево BFS dist[v] = dist[u] + 1; // відстань по шарах q.push(v); } } } return { dist, parent, visited }; } ``` ### Відновлення шляху (по parent) Після BFS можна відновити найкоротший шлях від s до t, підіймаючись по parent від t до s і розвертаючи послідовність. ``` function getPath(parent, s, t) { const path = []; for (let v = t; v !== -1; v = parent[v]) path.push(v); path.reverse(); return path[0] === s ? path : []; // якщо t недосяжний, повернемо порожній шлях } ``` ### Приклад: найкоротший шлях у неорієнтованому графі Граф заданий списками суміжності. Знайдемо найкоротший шлях від 0 до 5. ``` const adj = [ /*0*/ [1, 2], /*1*/ [0, 3, 4], /*2*/ [0, 4], /*3*/ [1, 5], /*4*/ [1, 2, 5], /*5*/ [3, 4] ]; const { dist, parent } = bfs(adj, 0); console.log('dist to 5:', dist[5]); // 3 console.log('path 0->5:', getPath(parent, 0, 5)); // наприклад [0,1,3,5] або [0,2,4,5] ``` ### Приклад: обхід дерева по рівнях (Level-Order Traversal) Для дерев BFS відповідає обходу по рівнях: спочатку корінь, потім усі вузли глибини 1, потім глибини 2 і так далі. ``` class Node { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } } function levelOrder(root) { if (!root) return []; const res = []; const q = [root]; let head = 0; while (head < q.length) { const levelSize = q.length - head; const level = []; for (let i = 0; i < levelSize; i++) { const node = q[head++]; level.push(node.val); if (node.left) q.push(node.left); if (node.right) q.push(node.right); } res.push(level); } return res; } // Приклад дерева: 1 // / \ // 2 3 // / \ \ // 4 5 6 const root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(6))); console.log(levelOrder(root)); // [[1],[2,3],[4,5,6]] ``` ### BFS на сітці (grid): найкоротший шлях із перешкодами Клітини зі значенням 0 - прохідні, 1 - перешкоди. Ходимо в 4 напрямках. BFS видасть довжину найкоротшого шляху в кроках. ``` function shortestPathGrid(grid, start, goal) { const m = grid.length, n = grid[0].length; const dirs = [[1,0],[-1,0],[0,1],[0,-1]]; const dist = Array.from({ length: m }, () => Array(n).fill(Infinity)); const q = []; let head = 0; const [sx, sy] = start, [gx, gy] = goal; if (grid[sx][sy] === 1 || grid[gx][gy] === 1) return -1; dist[sx][sy] = 0; q.push([sx, sy]); while (head < q.length) { const [x, y] = q[head++]; if (x === gx && y === gy) return dist[x][y]; for (const [dx, dy] of dirs) { const nx = x + dx, ny = y + dy; if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 0 && dist[nx][ny] === Infinity) { dist[nx][ny] = dist[x][y] + 1; q.push([nx, ny]); } } } return -1; // шляху до цілі немає } const grid = [ [0,0,1,0], [0,0,0,0], [1,0,1,0], [0,0,0,0] ]; console.log(shortestPathGrid(grid, [0,0], [3,3])); ``` ### Варіації і застосування - Найкоротші шляхи в неважених графах і сітках (у кроках/ребрах). - Визначення досяжності і відстаней від джерела до всіх вершин. - Перевірка зв'язності/підрахунок компонент зв'язності (запускаючи BFS із невідвіданих вершин). - Перевірка двочастковості графа: розфарбування по рівнях (чергування кольорів). - Мультиджерельний BFS: стартуємо з множини вершин одразу (відстань 0), корисно для задач «хвильового» поширення. ### BFS vs DFS - BFS використовує чергу і йде по шарах; DFS використовує стек/рекурсію і йде в глибину. - BFS знаходить найкоротший шлях у неважених графах; DFS такої гарантії не дає. - Пам'ять: BFS може споживати більше пам'яті на широких рівнях; DFS зазвичай економніший за пам'яттю. ### Коли BFS не підходить - Важені графи з різними вагами: потрібен Дейкстра (або 0-1 BFS для ваг 0/1, або A* з евристикою). - Дуже широкі графи/рівні - високе споживання пам'яті. ### Часті помилки - Позначати visited занадто пізно (при вилученні з черги), через що вузли можуть потрапити в чергу кілька разів. - Використовувати стек замість черги - отримаєте DFS, а не BFS. - Забувати ініціалізувати dist/parent/visited для кожного запуску BFS. - Неправильно враховувати напрямок ребер в орієнтованих графах.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.