Пошук у ширину: відмінності між версіями

Якщо задано граф ''G'' = (''V'', ''E'') та початкову вершину ''s'', алгоритм пошуку в ширину систематично обходить всі досяжні із ''s'' вершини. На першому кроці вершина ''s'' позначається, як пройдена, а в список додаються всі вершини, досяжні з ''s'' без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується [[Черга (структура даних)|черга]] та принцип [[Алгоритм заміщення комірок пам’яті FIFO|FIFO]]. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.