Пошук у ширину: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
АтаБот (обговорення | внесок) м виправлено порожній lang-xx, typos fixed: і т. п. → і т. ін. за допомогою AWB |
оновлення джерела |
||
Рядок 1:
[[Файл:Breadth-first-tree.svg|thumb|right|250px|Порядок обходу вершин.]]
[[Файл:Animated BFS.gif|thumb|right|250px|Ілюстрація пошуку у ширину. Чорні вершини пройдено, сірі чекають у черзі]]
'''По́шук у ширину́''' — [[алгоритм]] пошуку на [[граф (математика)|графі]]
{{ |author-link=Томас Кормен|first=Томас|last=Кормен|authorlink2=Чарльз Лейзерсон|first2=Чарльз|last2=Лейзерсон|authorlink3=Рональд Рівест|first3=Рональд|last3=Рівест|authorlink4=Кліфорд Стайн|first4=Кліфорд|last4=Стайн|year=2019|title=[[Вступ до алгоритмів]]|edition=3|publisher= [[К.І.С.]]|isbn=978-617-684-239-2
|chapter=Розділ 22.2: Пошук вшир
|pages=606–615}}
</ref>.
Якщо задано граф ''G'' = (''V'', ''E'') та початкову вершину ''s'', алгоритм пошуку в ширину систематично обходить всі досяжні із ''s'' вершини. На першому кроці вершина ''s'' позначається, як пройдена, а в список додаються всі вершини, досяжні з ''s'' без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується [[Черга (структура даних)|черга]] та принцип [[Алгоритм заміщення комірок пам’яті FIFO|FIFO]]. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.
| |||