![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Breadth-first-tree.svg/languk-640px-Breadth-first-tree.svg.png&w=640&q=50)
Пошук у ширину
З Вікіпедії, безкоштовно encyclopedia
По́шук у ширину́ — алгоритм пошуку на графі[1].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Breadth-first-tree.svg/320px-Breadth-first-tree.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/4/46/Animated_BFS.gif)
Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується черга та принцип FIFO. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.
Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.[1]